Subsets II

medium array backtracking bitmask

Problem

Given an integer array that may contain duplicates, return all possible unique subsets (the power set, with duplicate subsets removed).

Inputnums = [1, 2, 2]

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

Sort first; when iterating, skip nums[i] when it equals nums[i-1] at the same depth.

nums (comma-separated)

def subsets_with_dup(nums):
    nums.sort()
    out, cur = [], []
    def dfs(start):
        out.append(cur[:])
        for i in range(start, len(nums)):
            if i > start and nums[i] == nums[i - 1]: continue
            cur.append(nums[i])
            dfs(i + 1)
            cur.pop()
    dfs(0)
    return out

function subsetsWithDup(nums) {
  nums.sort((a, b) => a - b);
  const out = [], cur = [];
  function dfs(start) {
    out.push(cur.slice());
    for (let i = start; i < nums.length; i++) {
      if (i > start && nums[i] === nums[i - 1]) continue;
      cur.push(nums[i]);
      dfs(i + 1);
      cur.pop();
    }
  }
  dfs(0);
  return out;
}

class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> out = new ArrayList<>();
        dfs(nums, 0, new ArrayList<>(), out);
        return out;
    }
    private void dfs(int[] nums, int start, List<Integer> cur, List<List<Integer>> out) {
        out.add(new ArrayList<>(cur));
        for (int i = start; i < nums.length; i++) {
            if (i > start && nums[i] == nums[i - 1]) continue;
            cur.add(nums[i]);
            dfs(nums, i + 1, cur, out);
            cur.remove(cur.size() - 1);
        }
    }
}

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

Explanation

We want every unique subset of the array even though it can contain duplicates. We build subsets with backtracking, and add one small rule to avoid producing the same subset twice.

dfs(start) records the current subset cur the moment it is entered — that is how the empty set and every partial set get collected. Then it loops i from start onward, choosing to include nums[i], recursing from i + 1, and then removing it to try the next element.

The duplicate-skip rule is if i > start and nums[i] == nums[i-1]: continue. After sorting so equal values are adjacent, this says: at the same recursion depth, only use the first copy of a repeated value as a fresh starting choice. Skipping later copies at the same level avoids generating identical subsets.

Using start (instead of revisiting earlier indices) also keeps subsets in a consistent order, so we never list the same combination in a different arrangement.

Example: nums = [1, 2, 2]. The result is [], [1], [1,2], [1,2,2], [2], [2,2] — the duplicate [2] that the second 2 would create at the top level is correctly skipped.

Time: O(n · 2ⁿ) Space: O(n)