Permutations II

medium array backtracking

Problem

Given an integer array nums that might contain duplicates, return all possible unique permutations in any order.

Inputnums = [1, 1, 2]

Output[[1,1,2],[1,2,1],[2,1,1]]

Three unique orderings. Sort first, then skip nums[i] when it equals nums[i-1] and i-1 is unused at this level.

nums (comma-separated)

def permute_unique(nums):
    nums.sort()
    out, cur, used = [], [], [False] * len(nums)
    def dfs():
        if len(cur) == len(nums):
            out.append(cur[:]); return
        for i in range(len(nums)):
            if used[i]: continue
            if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
                continue
            used[i] = True; cur.append(nums[i])
            dfs()
            cur.pop(); used[i] = False
    dfs()
    return out

function permuteUnique(nums) {
  nums.sort((a, b) => a - b);
  const out = [], cur = [], used = new Array(nums.length).fill(false);
  function dfs() {
    if (cur.length === nums.length) { out.push(cur.slice()); return; }
    for (let i = 0; i < nums.length; i++) {
      if (used[i]) continue;
      if (i > 0 && nums[i] === nums[i - 1] && !used[i - 1]) continue;
      used[i] = true; cur.push(nums[i]);
      dfs();
      cur.pop(); used[i] = false;
    }
  }
  dfs();
  return out;
}

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

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> out;
        vector<int> cur;
        vector<bool> used(nums.size(), false);
        dfs(nums, used, cur, out);
        return out;
    }
    void dfs(vector<int>& nums, vector<bool>& used, vector<int>& cur, vector<vector<int>>& out) {
        if (cur.size() == nums.size()) { out.push_back(cur); return; }
        for (int i = 0; i < (int)nums.size(); i++) {
            if (used[i]) continue;
            if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;
            used[i] = true; cur.push_back(nums[i]);
            dfs(nums, used, cur, out);
            cur.pop_back(); used[i] = false;
        }
    }
};

Explanation

We need every unique ordering of the numbers, even though some numbers repeat. A plain permutation generator would produce the same ordering many times when there are duplicates, so the real challenge is skipping those repeats.

We build each permutation one slot at a time using backtracking. A used array marks which positions are already in the current arrangement. We pick an unused number, recurse, then un-pick it to try the next option.

The duplicate trick is the important part. First we sort so equal numbers sit next to each other. Then the line if i > 0 and nums[i] == nums[i-1] and not used[i-1]: continue says: if this number equals the one just before it and that earlier copy is not currently used, skip it. This forces equal numbers to always be picked in left-to-right order, so we never generate the same permutation twice.

When cur reaches the full length, we have a complete permutation and copy it into the answer.

Example: nums = [1, 1, 2]. After sorting it is still [1, 1, 2]. The rule blocks the second 1 from being placed before the first, so we get exactly three unique results: [1,1,2], [1,2,1], and [2,1,1].

Time: O(n · n!) Space: O(n)