47. Permutations II - cocoder39/coco39_LC GitHub Wiki

47. Permutations II

Notes 2020:

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        counters = collections.Counter(nums)
        res = []
        self.backtrack(len(nums), counters, [], res)
        return res
        
    def backtrack(self, l, counters, path, res):
        if len(path) == l:
            res.append(path[:])
            return
        
        for num in counters:
            if counters[num] > 0:
                path.append(num)
                counters[num] -= 1
                self.backtrack(l, counters, path, res)
                path.pop()
                counters[num] += 1

Time complexity: O(N * N!) Same as permutations

======================================================================================================

tricky is there are repeated elements, and the generated sequence should be unique.

  • sorting can make repeated elements be next to each other.
  • all unvisited element are candidates that can be put at this position. Among all those unvisited repeated elements, we choose only the first element.
t(n) = O(n) + n * t(n-1) 
t(n-1) = O(n) + (n-1) * t(n-2)
thus t(n) > O(n!)

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> cur;
        vector<bool> visited(nums.size());
        sort(nums.begin(), nums.end());
        helper(res, cur, visited, nums);
        return res;
    }
private:
    void helper(vector<vector<int>>& res, vector<int>& cur, vector<bool>& visited, vector<int>& nums) {
        if (cur.size() == nums.size()) {
            res.push_back(cur);
            return;
        }
        
        for (int i = 0; i < nums.size(); i++) { 
            if (! visited[i]) {
                //nums[i] and nums[i - 1] are racing only if they are equal and both are candidiates at current level
                if (i > 0 && ! visited[i - 1] && nums[i] == nums[i - 1]) {
                    continue;
                }
                visited[i] = true;
                cur.push_back(nums[i]);
                helper(res, cur, visited, nums);
                cur.pop_back();
                visited[i] = false;
            }
        }
    }
};
⚠️ **GitHub.com Fallback** ⚠️