Permutations II

Problem

Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.

Example 1:

Input: nums = [1,1,2]
Output:
[[1,1,2],
 [1,2,1],
 [2,1,1]]

Example 2:

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Constraints:

1 <= nums.length <= 8
-10 <= nums[i] <= 10

Solution

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permuteUnique = function(nums) {
    const res = [];
    const used = Array(nums.length).fill(false);
    backtrack(res, [], nums.sort(), used);
    return res;
};

var backtrack = function(res, path, nums, used) {
    if (path.length === nums.length) {
        res.push([...path]);
    } else {
        for (let i = 0; i < nums.length; i++) {
            if (used[i]) { // element already used
                continue;
            }
            if (i > 0 && nums[i] === nums[i - 1] && !used[i - 1]) { // duplicate
                continue;
            }
            used[i] = true;
            path.push(nums[i]);
            backtrack(res, path, nums, used);
            path.pop();
            used[i] = false;
        }
    }
};

We will implement a backtracking (DFS) solution. In our backtrack function, we use res to keep track of all valid permutations recorded so far, path to keep track of the current permutation, nums for all the available numbers, and used for values already in path. To retrieve only unique permutations, we must ensure duplicate numbers always appear in the same order (ie. if we have [1a, 1b, ...] we want 1a to always appear before 1b in path). This can be done by initially sorting nums and checking the condition i > 0 && nums[i] === nums[i - 1] && !(i - 1 in used). Note that since order matters for permutations, our loop must always start from 0.

Problem​

Solution​

Problem

Solution