Subsets II

Problem

You are given an array nums of integers, which may contain duplicates. Return all possible subsets.

The solution must not contain duplicate subsets. You may return the solution in any order.

Examples

Example 1:

Input: nums = [1,2,1]

Output: [[],[1],[1,2],[1,1],[1,2,1],[2]]

Example 2:

Input: nums = [7,7]

Output: [[],[7], [7,7]]

Constraints

• 1 <= nums.length <= 11
• -20 <= nums[i] <= 20

You should aim for a solution as good or better than O(n * (2^n)) time and O(n) space, where n is the size of the input array.

Solution

Regular DFS backtracking either includes or skips the element (we branch over 2 decisions). Because we are skipping repeats, we need to first sort, then skip over matching elements.

class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        std::vector<std::vector<int>> result;
        std::vector<int> current_subset;
        
        std::function<void(int)> dfs;
        dfs = [&](int i) {
            if (i == nums.size()) { 
                result.push_back(current_subset);
                return;
            }
            // Option 1: Add this item to the set
            current_subset.push_back(nums[i]);
            dfs(i + 1);
            current_subset.pop_back();
 
            // Option 2: Skip this element (and all matching values)
            while (i + 1 < nums.size() && nums[i] == nums[i + 1]) {
                ++i;
            }
            dfs(i + 1);
        };
 
        std::ranges::sort(nums);
        dfs(0);
        return result;
    }
};