Subsets II — Solution in Python, Java & C++
Subsets II solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem, asked at Amazon and Meta.
Subsets II is a medium coding problem on arrays, bit manipulation and backtracking, asked in Amazon, Meta and Bloomberg interviews.
- Difficulty: Medium
- Topics: Arrays, Bit Manipulation, Backtracking
- Asked at: Amazon, Meta, Bloomberg
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
nums is an integer array that may contain repeated values. Return every subset of it (its power set), with no subset appearing twice. Two subsets are the same when they hold the same values with the same multiplicities, whichever positions they were taken from.
Write each subset in non-decreasing order, and list the subsets in lexicographic order: compare two subsets value by value from the left; when one is a prefix of the other, the shorter one comes first. So the empty subset is always first.
Example 1
Input: nums = [1,2,2]
Output: [[],[1],[1,2],[1,2,2],[2],[2,2]]
Explanation: Picking either of the two 2s gives the same subset `[1,2]`, so it is listed once.
Example 2
Input: nums = [0]
Output: [[],[0]]
Example 3
Input: nums = [4,4,1,4]
Output: [[],[1],[1,4],[1,4,4],[1,4,4,4],[4],[4,4],[4,4,4]]
Constraints
1 <= nums.length <= 10-10 <= nums[i] <= 10
Hints for Subsets II
Hint 1
Sort the array first, so equal values sit next to each other and every subset is built in non-decreasing order.
Hint 2
Build subsets by choosing which index comes next. Record the current subset every time you enter the recursion, before extending it.
Hint 3
At one level of the recursion, try each distinct value only once: skip index
iwheni > startandnums[i] == nums[i - 1]. Visiting the values in increasing order makes the output lexicographic for free.
How to solve Subsets II
After sorting, a subset is a non-decreasing sequence of values, and a subset is a duplicate exactly when the same value is chosen twice as the next element at the same depth. Skipping repeated values at each level removes every duplicate without a hash set.
Approach
- Sort
nums. - Run
dfs(start)with a sharedpath: first append a copy ofpathto the answer. - Then for every
ifromstartto the end, skip it ifi > startandnums[i] == nums[i - 1]; otherwise pushnums[i], calldfs(i + 1), and pop. - Call
dfs(0)and return the collected subsets.
Why it works
Each distinct subset, written in sorted order, has exactly one leftmost way of being picked: for each value, take its copies from the earliest equal positions. The skip rule allows only that choice, so every subset is produced exactly once. The order is lexicographic because a subset is emitted before its extensions (a prefix comes first) and the children of a node are explored in increasing order of their next value.
Complexity
- Time —
O(n · 2^n) - Space —
O(n) besides the output
Pitfalls
- The skip test is
i > start, noti > 0— the first copy of a value at a new depth must still be usable, which is how[2,2]is formed. - Push a copy of
path, notpathitself, or every entry ends up as the same mutated list. - Without sorting, equal values are not adjacent and the skip rule misses duplicates.
Reference solution
Python
from typing import List
def subsetsWithDup(nums: List[int]) -> List[List[int]]:
a = sorted(nums)
out = []
path = []
def dfs(start):
out.append(path[:])
for i in range(start, len(a)):
if i > start and a[i] == a[i - 1]:
continue
path.append(a[i])
dfs(i + 1)
path.pop()
dfs(0)
return outJava
public static int[][] subsetsWithDup(int[] nums) {
int[] a = nums.clone();
Arrays.sort(a);
List<int[]> out = new ArrayList<>();
subsetsDfs(a, 0, new int[a.length], 0, out);
return out.toArray(new int[0][]);
}
static void subsetsDfs(int[] a, int start, int[] path, int len, List<int[]> out) {
out.add(Arrays.copyOf(path, len));
for (int i = start; i < a.length; i++) {
if (i > start && a[i] == a[i - 1]) continue;
path[len] = a[i];
subsetsDfs(a, i + 1, path, len + 1, out);
}
}C++
void subsetsDfs(vector<int>& a, int start, vector<int>& path, vector<vector<int>>& out) {
out.push_back(path);
for (int i = start; i < (int)a.size(); i++) {
if (i > start && a[i] == a[i - 1]) continue;
path.push_back(a[i]);
subsetsDfs(a, i + 1, path, out);
path.pop_back();
}
}
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
vector<int> a(nums.begin(), nums.end());
sort(a.begin(), a.end());
vector<vector<int>> out;
vector<int> path;
subsetsDfs(a, 0, path, out);
return out;
}JavaScript
var subsetsWithDup = function(nums) {
var a = nums.slice().sort(function(x, y) { return x - y; });
var out = [];
var path = [];
var dfs = function(start) {
out.push(path.slice());
for (var i = start; i < a.length; i++) {
if (i > start && a[i] === a[i - 1]) continue;
path.push(a[i]);
dfs(i + 1);
path.pop();
}
};
dfs(0);
return out;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Bit Manipulation