90. Subsets II - cocoder39/coco39_LC GitHub Wiki

90. Subsets II

Notes 2020:

[1,2,2]

[] -> 1 -> 1,2 -> 1,2,2
   -> 2 -> 2,2

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        res = []
        self.helper(nums, 0, [], res)
        return res
    
    def helper(self, nums, start, path, res):
        res.append(path[:])
        
        for i in range(start, len(nums)):
            if i > start and nums[i] == nums[i-1]:
                continue
            path.append(nums[i])
            self.helper(nums, i+1, path, res)
            path.pop()

Time complexity: Upper bound is same as problem Subsets O(N * 2^N). 2^n solutions and each requires a deep copy

This is simply extending the new approach adopted in problem Subsets to avoid duplicated number. By consistently applying this thinking process, related problems can all be solved with same pattern.

solution 2: use hash to de-dup

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:

        def helper(start, path, res):
            res.add(tuple(sorted(path)))

            for i in range(start, len(nums)):
                path.append(nums[i])
                helper(i+1, path, res)
                path.pop()
        
        res = set()
        helper(0, [], res)
        return list(res)

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

use sort to get rid of duplication. remember to pop back for backtracking

given [1, 2, 2]

[] -> [], [2], [2, 2]
[1] => [2, 2, 1] -> [2, 2, 1], [2, 2, 1, 2], [2, 2, 1, 2, 2]

time is O(2^n), space for call stack is O(h) where h = n

class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> cur;
        sort(nums.begin(), nums.end());
        helper(res, cur, nums, 0);
        return res;
    }
private:
    void helper(vector<vector<int>>& res, vector<int>& cur, vector<int>& nums, int start) {
        if (start == nums.size()) {
            res.push_back(cur);
            return;
        }
        
        //[start, end)
        int end = start + 1;
        while (end < nums.size() && nums[end] == nums[start])   end++;
        
//append one, pop back one
        helper(res, cur, nums, end);
        for (int i = start; i < end; i++) {
            cur.push_back(nums[start]);
            helper(res, cur, nums, end);
        }
        for (int i = start; i < end; i++)   cur.pop_back();
    }
};
⚠️ **GitHub.com Fallback** ⚠️