47. Permutations II

Description

The problem is to generate all unique permutations of a list of integers, where the list may contain duplicate elements. For example, given the list [1, 1, 2], the unique permutations are [[1, 1, 2], [1, 2, 1], [2, 1, 1]].

Intuition

When dealing with permutations where duplicates are present, a straightforward approach can generate duplicate permutations. To handle this, we need to ensure that each permutation is unique. A common technique is to use a backtracking approach combined with a set to track the permutations we've already encountered. By generating permutations recursively and using a set to check for uniqueness, we can avoid adding duplicates to our result.

Approach

1. Sorting: First, sort the input list to facilitate easy skipping of duplicates.
2. Backtracking: Use a recursive function to generate permutations. Keep track of the current permutation and a flag array to mark which elements are used.
3. Uniqueness: Use a set to track and avoid adding duplicate permutations. Convert each permutation to a string key to ensure that each permutation is unique.
4. Base Case: If the current permutation has the same length as the input list, add it to the result list if it hasn't been added before.
5. Recursive Case: Iterate through the list, skipping over duplicates using the sorted property and the flag array.

Complexity

Time Complexity:

The time complexity is (O(N!)), where (N) is the number of elements in the list. This is because there are (N!) possible permutations, and each permutation is generated and checked.

Space Complexity:

The space complexity is (O(N \cdot N!)). The space is used for storing all unique permutations (which can be (N!) permutations, each of length (N)) and the recursion stack, which can go up to (O(N)) depth.

Code

C++

class Solution {
public:
    vector> permuteUnique(vector& nums) {
        vector> res;
        vector ds;
        vector flag(nums.size(), false);
        unordered_set keys;

        sort(nums.begin(), nums.end());
        backtrack(0, nums, ds, flag, keys, res);
        return res;
    }

private:
    void backtrack(int ind, vector& nums, vector& ds, vector& flag, unordered_set& keys, vector>& res) {
        if (ds.size() == nums.size()) {
            string key = createKey(ds);
            if (keys.find(key) == keys.end()) {
                keys.insert(key);
                res.push_back(ds);
            }
            return;
        }

        for (int i = 0; i < nums.size(); i++) {
            if (!flag[i]) {
                ds.push_back(nums[i]);
                flag[i] = true;
                backtrack(i + 1, nums, ds, flag, keys, res);
                ds.pop_back();
                flag[i] = false;
            }
        }
    }

    string createKey(vector& ds) {
        string key;
        for (int num : ds) {
            key += to_string(num) + '_';
        }
        return key;
    }
};

Python

class Solution:
    def permuteUnique(self, nums):
        res = []
        keys = set()
        
        def backtrack(ind, ds, flag):
            if len(ds) == len(nums):
                key = '_'.join(map(str, ds))
                if key not in keys:
                    keys.add(key)
                    res.append(ds[:])
                return
            
            for i in range(len(nums)):
                if not flag[i]:
                    ds.append(nums[i])
                    flag[i] = True
                    backtrack(i + 1, ds, flag)
                    ds.pop()
                    flag[i] = False
        
        backtrack(0, [], [False] * len(nums))
        return res

Java

class Solution {
    public List> permuteUnique(int[] nums) {
        List> res = new ArrayList<>();
        List ds = new ArrayList<>();
        boolean[] flag = new boolean[nums.length];
        Set keys = new HashSet<>();

        java.util.Arrays.sort(nums);
        backtrack(0, nums, ds, flag, keys, res);
        return res;
    }

    private void backtrack(int ind, int[] nums, List ds, boolean[] flag, Set keys, List> res) {
        if (ds.size() == nums.length) {
            String key = createKey(ds);
            if (!keys.contains(key)) {
                keys.add(key);
                res.add(new ArrayList<>(ds));
            }
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (!flag[i]) {
                ds.add(nums[i]);
                flag[i] = true;
                backtrack(i + 1, nums, ds, flag, keys, res);
                ds.remove(ds.size() - 1);
                flag[i] = false;
            }
        }
    }

    private String createKey(List ds) {
        StringBuilder key = new StringBuilder();
        for (int num : ds) {
            key.append(num).append('_');
        }
        return key.toString();
    }
}

JavaScript

var permuteUnique = function (nums) {

    const res = [];
    const keys = [];

    function f(ind, ds, flag) {
        if (ds.length == nums.length) {
            const key = ds.join('_');
            if (keys.indexOf(key) == -1) {
                keys.push(key);
                res.push([...ds]);
            }
            return;
        }
        for (let i = 0; i < nums.length; i++) {
            if (!flag[i]) {
                ds.push(nums[i]);
                flag[i] = 1;
                f(i + 1, ds, flag);
                ds.pop();
                flag[i] = 0;
            }
        }
    }
    f(0, [], {});
    return res;
};