Subsets II [Medium] — Backtracking with Duplicate Skip

Problem Statement

Given an integer array that may contain duplicates, return all possible unique subsets (no duplicate subsets in output).

Input: [1,2,2] → Output: [[],[1],[1,2],[1,2,2],[2],[2,2]]

Intuition

Sort + backtrack. At each recursion level, skip nums[i] if i > start and nums[i] == nums[i-1] (same as Combination Sum II trick).

Solutions

C++

vector<vector<int>> subsetsWithDup(vector<int>& nums) {
    sort(nums.begin(),nums.end());
    vector<vector<int>> res; vector<int> cur;
    function<void(int)> dfs=[&](int start){
        res.push_back(cur);
        for(int i=start;i<nums.size();i++){
            if(i>start&&nums[i]==nums[i-1]) continue;
            cur.push_back(nums[i]); dfs(i+1); cur.pop_back();
        }
    };
    dfs(0); return res;
}

Python

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

Complexity

Time: O(2^n × n)
Space: O(n)