Permutations II

Problem

Given an array that may contain duplicates, return all distinct permutations.

Constraints

• 1 ≤ n ≤ 8

Approach — Backtracking

This is a Backtracking problem. The idea: build candidates one choice at a time and abandon a branch the moment it can't lead to a valid answer. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: exponential worst case.

Solution code

Python

class Solution:
    def permuteUnique(self, nums):
        nums.sort()
        res = []
        used = [False] * len(nums)
        def bt(cur):
            if len(cur) == len(nums):
                res.append(cur[:]); return
            for i in range(len(nums)):
                if used[i] or (i > 0 and nums[i] == nums[i-1] and not used[i-1]):
                    continue
                used[i] = True; cur.append(nums[i])
                bt(cur)
                cur.pop(); used[i] = False
        bt([])
        return res

Java

import java.util.*;
class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> out = new ArrayList<>();
        bt(out, new ArrayList<>(), nums, new boolean[nums.length]);
        return out;
    }
    private void bt(List<List<Integer>> out, List<Integer> cur, int[] a, boolean[] used) {
        if (cur.size() == a.length) { out.add(new ArrayList<>(cur)); return; }
        for (int i = 0; i < a.length; i++) {
            if (used[i]) continue;
            if (i > 0 && a[i] == a[i-1] && !used[i-1]) continue;
            used[i] = true;
            cur.add(a[i]);
            bt(out, cur, a, used);
            cur.remove(cur.size() - 1);
            used[i] = false;
        }
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.