Subsets II

How it works

This iterative method builds subsets step by step. Normally, for each new number, we add it to every existing subset. But duplicates cause repeated subsets — so we must avoid recombining duplicates with all previous subsets.

Key idea:

• Sort the array so duplicates are next to each other.
• Maintain two indices:
  • idx: start point for generating new subsets.
  • prev_idx: end point (previous size of result list before adding this number).
• If the current number is not a duplicate, we start from the beginning (idx = 0).
• If it is a duplicate, we only combine it with subsets created in the last round. This prevents duplicate subsets from being generated.

Example: For input [1,2,2]

• First 2 extends all subsets.
• Second 2 extends only the subsets added when first 2 was processed → no duplicates.

Steps

1. Sort nums so duplicates are adjacent.
2. Initialize res = [[]].
3. For each index i:
   • If nums[i] is the same as nums[i-1] → set idx to the previous end (prev_idx).
   • Otherwise → set idx = 0.
   • Set prev_idx = len(res) (the boundary of old subsets).
   • For every subset res[j] where j ranges from idx to prev_idx - 1:
     • Create a new subset by appending nums[i].
     • Add it to res.
4. Return res.

Complexity

• Time complexity: O(n * 2 ^ n)
• Space complexity:
  • O(1) extra space.
  • O(2 ^ n) space for the output list.

Things to watch for

Forgetting to Sort the Array First

Sorting is essential because it groups duplicate elements together, enabling the skip logic to work correctly. Without sorting, duplicates scattered throughout the array cannot be detected and skipped, resulting in duplicate subsets.

Incorrect Duplicate Skipping Condition

The condition j > i && nums[j] == nums[j-1] must use j > i, not j > 0 or j >= i. Using j > 0 would skip the first occurrence of a duplicate at each recursion level, missing valid subsets. The check ensures we only skip duplicates after the first one at the current decision level.

Modifying the Subset Reference Incorrectly

When adding subsets to the result, you must copy the current subset (e.g., subset[:] in Python or new ArrayList<>(subset) in Java). Adding the reference directly means all entries in the result will point to the same list, which gets modified during backtracking.

from typing import List

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        res = [[]]
        prev_Idx = idx = 0

        for i in range(len(nums)):
            idx = prev_idx if i >= 1 and nums[i] == nums[i - 1] else 0
            prev_idx = len(res)
            for j in range(idx, prev_idx):
                tmp = res[j].copy()
                tmp.append(nums[i])
                res.append(tmp)

        return res

class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> res = {{}};
        int prevIdx = 0;
        int idx = 0;

        for (int i = 0; i < nums.size(); i++) {
            idx = (i >= 1 && nums[i] == nums[i - 1]) ? prevIdx : 0;
            prevIdx = res.size();
            for (int j = idx; j < prevIdx; j++) {
                std::vector<int> tmp = res[j];
                tmp.push_back(nums[i]);
                res.push_back(tmp);
            }
        }

        return res;
    }
};