Subsets II

Problem Description

Given an integer array nums that may contain duplicates, return all possible subsets (the power set).

The solution set must not contain duplicate subsets. Return the solution in any order.

Examples

Constraints

• 1 ≤ nums.length ≤ 10
• -10 ≤ nums[i] ≤ 10

One Condition Separates This from Subsets

Subsets I guarantees unique elements. Subsets II doesn’t. The output still can’t have duplicate subsets, which means [1,2] should appear once even if there are two 2s in the input.

Sort the array. Now all duplicates are adjacent. The rule: at each recursion depth, if you’re considering an element that’s the same as the previous element you tried at this same depth, skip it. This prevents generating the same subset twice at the same branch level.

Solution: Sorted Backtracking

import java.util.*;

class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();
        backtrack(nums, 0, new ArrayList<>(), result);
        return result;
    }

    private void backtrack(int[] nums, int start,
                            List<Integer> current, List<List<Integer>> result) {
        result.add(new ArrayList<>(current));

        for (int i = start; i < nums.length; i++) {
            // skip duplicate values at the same recursion level
            if (i > start && nums[i] == nums[i - 1]) continue;

            current.add(nums[i]);
            backtrack(nums, i + 1, current, result);
            current.remove(current.size() - 1);
        }
    }
}

class Solution:
    def subsetsWithDup(self, nums: list[int]) -> list[list[int]]:
        nums.sort()
        result = []

        def backtrack(start: int, current: list[int]):
            result.append(current[:])

            for i in range(start, len(nums)):
                # skip duplicate values at the same recursion level
                if i > start and nums[i] == nums[i - 1]:
                    continue

                current.append(nums[i])
                backtrack(i + 1, current)
                current.pop()

        backtrack(0, [])
        return result

#include <vector>
#include <algorithm>

class Solution {
public:
    std::vector<std::vector<int>> subsetsWithDup(std::vector<int>& nums) {
        std::sort(nums.begin(), nums.end());
        std::vector<std::vector<int>> result;
        std::vector<int> current;
        backtrack(nums, 0, current, result);
        return result;
    }

private:
    void backtrack(std::vector<int>& nums, int start,
                   std::vector<int>& current,
                   std::vector<std::vector<int>>& result) {
        result.push_back(current);

        for (int i = start; i < (int)nums.size(); i++) {
            if (i > start && nums[i] == nums[i - 1]) continue;

            current.push_back(nums[i]);
            backtrack(nums, i + 1, current, result);
            current.pop_back();
        }
    }
};

Complexity Analysis:

• Time Complexity: O(n * 2^n). Even with duplicates, in the worst case (all unique elements) you generate 2^n subsets.
• Space Complexity: O(n) recursion depth.

Where it breaks: the check i > start matters. If you use i > 0 instead, you skip duplicate values even when they’re at different recursion levels, which would drop valid subsets like [1,2,2] entirely.

Common Mistakes

• i > 0 vs i > start for the duplicate skip. Always i > start. The skip should only apply when you’re reconsidering the same choice at the same recursion level.
• Not sorting first. The skip logic only works when equal values are adjacent. Without sorting, duplicate detection fails.
• Confusing this with Subsets I. In Subsets I, elements are guaranteed unique so no skip is needed. In Subsets II, the skip is mandatory.

Frequently Asked Questions

What does i > start && nums[i] == nums[i-1] actually prevent? It prevents picking the same value more than once at the same level of recursion. For [1,2,2], at start=1, you’d consider nums[1]=2 and nums[2]=2. The condition skips nums[2] since we already explored what happens when we pick 2 first at this level.

How does this extend to Permutations II? Same idea: sort first, use a used array, and skip nums[i] if nums[i] == nums[i-1] and !used[i-1]. The extra !used[i-1] condition handles the permutation case where position matters.

← All Problems