Subsets II

mediumBacktracking54 stepsJava · Python · C++

Generate all subsets when the input has duplicates, without repeating any subset. Sort so equal values are adjacent; at each level, skip a value if it equals the previous value tried at the same level.

▶ Watch the animated trace

Traced input: nums = [1, 2, 2] → [[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]. Original problem: neetcode.io/problems/subsets-ii

Complexity

BestO(n·2ⁿ)

AverageO(n·2ⁿ)

WorstO(n·2ⁿ)

SpaceO(n)

Worst case all distinct.

Key idea

Sorting puts duplicates next to each other.
i > start && nums[i] == nums[i-1] means the same value was already tried at this level.
Using a duplicate deeper in the tree (i == start) is allowed: that's how [2, 2] is formed.

Common mistakes

Skipping with i > 0 instead of i > start loses subsets like [2, 2].
Deduplicating with a Set of lists works but is slower.

Solution

Java

List<List<Integer>> subsetsWithDup(int[] nums) {
    Arrays.sort(nums);
    List<List<Integer>> res = new ArrayList<>();
    go(nums, 0, new ArrayList<>(), res);
    return res;
}

void go(int[] nums, int start, List<Integer> path, List<List<Integer>> res) {
    res.add(new ArrayList<>(path));
    for (int i = start; i < nums.length; i++) {
        if (i > start && nums[i] == nums[i - 1]) {
            continue;
        }
        path.add(nums[i]);
        go(nums, i + 1, path, res);
        path.remove(path.size() - 1);
    }
}

Python

def subsetsWithDup(nums: List[int]) -> List[List[int]]:
    nums.sort()
    res = []

    def go(start: int, path: List[int]) -> None:
        res.append(path[:])
        for i in range(start, len(nums)):
            if i > start and nums[i] == nums[i - 1]:
                continue
            path.append(nums[i])
            go(i + 1, path)
            path.pop()

    go(0, [])
    return res

C++

void go(vector<int>& nums, int start, vector<int>& path, vector<vector<int>>& res) {
    res.push_back(path);
    for (int i = start; i < (int)nums.size(); i++) {
        if (i > start && nums[i] == nums[i - 1]) {
            continue;
        }
        path.push_back(nums[i]);
        go(nums, i + 1, path, res);
        path.pop_back();
    }
}

vector<vector<int>> subsetsWithDup(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    vector<vector<int>> res;
    vector<int> path;
    go(nums, 0, path, res);
    return res;
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
All duplicates One subset per count.	`nums = [2, 2, 2]`	`[[], [2], [2, 2], [2, 2, 2]]`
Unsorted input Sorting first is what makes the skip work.	`nums = [4, 1, 4]`	`[[], [1], [1, 4], [1, 4, 4], [4], [4, 4]]`
Single element No duplicates to skip.	`nums = [0]`	`[[], [0]]`