Subsets II

Medium Problem 86 of 151 Java and Python

Problem

Given an integer array nums that may contain duplicates, return all possible subsets. The answer must not contain duplicate subsets; return them in any order.

Example 1

Input: nums = [1, 2, 2]
Output: [[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]

Example 2

Input: nums = [0]
Output: [[], [0]]

Constraints

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

Explanation

Sort first so equal values sit together. Then, at one level of the recursion, choosing the first 2 or the second 2 as the next element leads to identical subsets, so only try the first of each run of equal values.

Approach 1 · Naive

All subsets, deduplicated with a set

Time O(n · 2ⁿ)
Space O(n · 2ⁿ) for the set

Sort, generate all 2ⁿ subsets (each comes out sorted), and drop repeats with a set.

Sort nums.
Generate subsets by bitmask and add each to a set.
Return the set as a list.

Java

import java.util.*;

class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        Set<List<Integer>> seen = new LinkedHashSet<>();
        for (int mask = 0; mask < (1 << nums.length); mask++) {
            List<Integer> subset = new ArrayList<>();
            for (int i = 0; i < nums.length; i++) {
                if ((mask & (1 << i)) != 0) {
                    subset.add(nums[i]);
                }
            }
            seen.add(subset);
        }
        return new ArrayList<>(seen);
    }
}

Python

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        nums = sorted(nums)
        n = len(nums)
        seen = {tuple(nums[i] for i in range(n) if mask >> i & 1) for mask in range(1 << n)}
        return [list(s) for s in seen]

Approach 2 · Optimal

Backtracking that skips duplicates

Time O(n · 2ⁿ)
Space O(n) recursion besides the output

Sort, then in the loop skip nums[i] when it equals nums[i - 1] and i is not the first choice at this depth.

Sort nums.
backtrack(start): record path. For i from start: if i > start and nums[i] == nums[i - 1], skip.
Otherwise push, recurse with i + 1, pop.

Java

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> path, List<List<Integer>> result) {
        result.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]);
            backtrack(nums, i + 1, path, result);
            path.remove(path.size() - 1);
        }
    }
}

Python

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        nums = sorted(nums)
        result, path = [], []

        def backtrack(start):
            result.append(path[:])
            for i in range(start, len(nums)):
                if i > start and nums[i] == nums[i - 1]:
                    continue
                path.append(nums[i])
                backtrack(i + 1)
                path.pop()

        backtrack(0)
        return result

Complexity compared

Approach	Time	Space
Naive All subsets, deduplicated with a set	O(n · 2ⁿ)	O(n · 2ⁿ) for the set
Optimal Backtracking that skips duplicates	O(n · 2ⁿ)	O(n) recursion besides the output

Key takeaways

The condition is i > start, not i > 0: picking a duplicate is fine as long as it is not the same choice at the same depth.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem