Subsets II solution and explanation
TCS
Google
9 more videos on this problem
Subsets II - Backtracking - Leetcode 90 - PythonNeetCode · 15:05 · 171K views
Subsets 2 (LeetCode 90) | Full solution with backtracking examples | Interview | Study AlgorithmsNikhil Lohia · 11:44 · 22K views
Leetcode 90. Subsets II [ Backtracking Algorithm + Code Explained] TC - O(N * 2^N)jayati tiwari · 7:11 · 10K views
LeetCode Tutorial 90. Subsets IIGoodTecher · 16:13 · 7K views
Subsets II - LeetCode #90 with python programmingCodingNinja · 11:37 · 2K views
Baozi Training Leetcode 90 solution: Subsets IIBaozi Training · 4:26 · 1K views
LeetCode 90. Subsets IIHappy Coding · 9:59 · 1K views
Subsets II - LeetCode 90 - JavaScriptAlgoJS · 6:12 · 914 views
90. Subsets II (Leetcode Medium)Programming Live with Larry · 10:22 · 526 views
Leetcode 90 Subset II (Bit Manipulation)Gautam Sharma · 12:40 · 464 views
The problem
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.
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
Approach overview
Problem Overview: Given an integer array that may contain duplicate values, generate all possible subsets (the power set) while ensuring the result does not contain duplicate subsets. The main challenge is handling repeated elements so the same subset is not generated multiple times.
Approach 1: Backtracking with Sorting (O(n·2^n) time, O(n) extra space)
This approach uses backtracking to explore every subset possibility while preventing duplicates during recursion. First, sort the array so duplicate elements appear next to each other. During the recursive DFS, iterate from the current index and build the subset step by step. When encountering a duplicate value at the same recursion depth, skip it using a condition like if (i > start && nums[i] == nums[i-1]) continue. This ensures the algorithm only uses the first occurrence of each duplicate at a given level. The recursion tree explores include/exclude decisions and builds subsets incrementally. Time complexity is O(n·2^n) because up to 2^n subsets are generated and each subset copy may cost O(n). Space complexity is O(n) for the recursion stack (excluding output). This is the most common and interview-friendly solution.
Approach 2: Iterative Subset Construction (O(n·2^n) time, O(n·2^n) space)
This method builds subsets iteratively instead of recursion. Start with a result list containing an empty subset. Sort the array first so duplicates can be detected. For each number, iterate through the existing subsets and append the current number to create new subsets. When the current number is a duplicate of the previous one, only extend the subsets that were added in the previous step instead of all subsets. Tracking the starting index of newly created subsets prevents duplicate combinations. This technique treats subset generation as incremental expansion of the result list. Time complexity remains O(n·2^n) because every element can double the number of subsets. Space complexity is O(n·2^n) since all subsets are stored explicitly.
Both solutions rely on sorting the input array, a common pattern when working with duplicates in array problems. Some implementations also demonstrate subset generation using bit manipulation, but handling duplicates with bit masks typically requires additional filtering and is less practical here.
Recommended for interviews: Backtracking with sorting is the expected solution. It clearly demonstrates recursion, pruning, and duplicate handling using sorted input. Interviewers often want to see how you avoid generating duplicate subsets instead of filtering them afterward. The iterative construction method is also valid and useful if you prefer non-recursive solutions, but the backtracking approach better demonstrates algorithmic reasoning.
Approach 1: Approach 1: Backtracking with Sorting
In this approach, the problem of subsets with duplicates is solved by first sorting the array. This assists in easily identifying and omitting duplicates. The backtracking method is utilized to construct all possible subsets, ensuring no duplicate subsets are generated by skipping duplicate numbers during recursive backtracking.
from typing import List
def subsetsWithDup(nums: List[int]) -> List[List[int]]:
def backtrack(start: int, path: List[int]):
result.append(path.copy())
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)
path.pop()
nums.sort()
result = []
backtrack(0, [])
return result
# Example Usage
d = subsetsWithDup([1, 2, 2])
for subset in d:
print(subset)import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Solution {
public List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> result = new ArrayList<>();
backtrack(result, new ArrayList<>(), nums, 0);
return result;
}
private void backtrack(List<List<Integer>> result, List<Integer> tempList, int[] nums, int start) {
result.add(new ArrayList<>(tempList));
for (int i = start; i < nums.length; i++) {
if (i > start && nums[i] == nums[i - 1]) continue; // skip duplicates
tempList.add(nums[i]);
backtrack(result, tempList, nums, i + 1);
tempList.remove(tempList.size() - 1);
}
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] nums = {1, 2, 2};
List<List<Integer>> result = solution.subsetsWithDup(nums);
for (List<Integer> subset : result) {
System.out.println(subset);
}
}
}#include <iostream>
#include <vector>
#include <algorithm>
class Solution {
public:
void backtrack(std::vector<int>& nums, std::vector<std::vector<int>>& ans, std::vector<int>& current, int start) {
ans.push_back(current);
for (int i = start; i < nums.size(); ++i) {
if (i > start && nums[i] == nums[i - 1]) continue;
current.push_back(nums[i]);
backtrack(nums, ans, current, i + 1);
current.pop_back();
}
}
std::vector<std::vector<int>> subsetsWithDup(std::vector<int>& nums) {
std::sort(nums.begin(), nums.end());
std::vector<std::vector<int>> ans;
std::vector<int> current;
backtrack(nums, ans, current, 0);
return ans;
}
};
int main() {
Solution solution;
std::vector<int> nums = {1, 2, 2};
std::vector<std::vector<int>> result = solution.subsetsWithDup(nums);
for (const auto& subset : result) {
std::cout << "[";
for (size_t i = 0; i < subset.size(); ++i) {
std::cout << subset[i] << (i + 1 < subset.size() ? ", " : "");
}
std::cout << "]\n";
}
return 0;
}function subsetsWithDup(nums) {
nums.sort((a, b) => a - b);
const result = [];
function backtrack(start, path) {
result.push([...path]);
for (let i = start; i < nums.length; i++) {
if (i > start && nums[i] === nums[i - 1]) continue;
path.push(nums[i]);
backtrack(i + 1, path);
path.pop();
}
}
backtrack(0, []);
return result;
}
// Example Usage
console.log(subsetsWithDup([1, 2, 2]));#include <stdio.h>
#include <stdlib.h>
// Compare function for qsort
int cmp(const void *a, const void *b) {
return (*(int *)a - *(int *)b);
}
void backtrack(int *nums, int numsSize, int **results, int *resultSizes, int *columnSizes, int *temp, int tempSize, int start, int *returnSize) {
// Allocate memory for current subset and add it to the results
resultSizes[*returnSize] = tempSize;
results[*returnSize] = malloc(resultSizes[*returnSize] * sizeof(int));
for (int i = 0; i < tempSize; ++i) results[*returnSize][i] = temp[i];
(*returnSize)++;
for (int i = start; i < numsSize; ++i) {
if (i > start && nums[i] == nums[i - 1]) continue; // Skip duplicates
temp[tempSize] = nums[i];
backtrack(nums, numsSize, results, resultSizes, columnSizes, temp, tempSize + 1, i + 1, returnSize);
}
}
int **subsetsWithDup(int *nums, int numsSize, int *returnSize, int **returnColumnSizes) {
int maxSize = 1 << numsSize;
int **results = malloc(maxSize * sizeof(int *));
*returnColumnSizes = malloc(maxSize * sizeof(int));
int *temp = malloc(numsSize * sizeof(int));
*returnSize = 0;
qsort(nums, numsSize, sizeof(int), cmp);
backtrack(nums, numsSize, results, *returnColumnSizes, *returnColumnSizes, temp, 0, 0, returnSize);
free(temp);
return results;
}
int main() {
int nums[] = {1, 2, 2};
int size = sizeof(nums) / sizeof(nums[0]);
int returnSize;
int *returnColumnSizes;
int **result = subsetsWithDup(nums, size, &returnSize, &returnColumnSizes);
for (int i = 0; i < returnSize; ++i) {
printf("[");
for (int j = 0; j < returnColumnSizes[i]; ++j) {
printf("%d%c", result[i][j], j == returnColumnSizes[i] - 1 ? ' ' : ', ');
}
printf("]\n");
free(result[i]);
}
free(result);
free(returnColumnSizes);
return 0;
}using System;
using System.Collections.Generic;
class Solution {
public IList<IList<int>> SubsetsWithDup(int[] nums) {
Array.Sort(nums);
IList<IList<int>> result = new List<IList<int>>();
Backtrack(result, new List<int>(), nums, 0);
return result;
}
private void Backtrack(IList<IList<int>> result, IList<int> tempList, int[] nums, int start) {
result.Add(new List<int>(tempList));
for (int i = start; i < nums.Length; i++) {
if (i > start && nums[i] == nums[i - 1]) continue;
tempList.Add(nums[i]);
Backtrack(result, tempList, nums, i + 1);
tempList.RemoveAt(tempList.Count - 1);
}
}
public static void Main(string[] args) {
Solution solution = new Solution();
var result = solution.SubsetsWithDup(new int[] { 1, 2, 2 });
foreach (var subset in result) {
Console.WriteLine("[" + string.Join(", ", subset) + "]");
}
}
}This Python solution also uses sorting followed by a recursive backtracking method to eliminate duplicate subsets. It accomplishes this by checking and skipping duplicates.
The time complexity is O(2^n * n), where each subset is derived and processed. The space complexity involves space for call stacks and temporary path storage, maintaining an average complexity of O(n).
Approach 2: Approach 2: Iterative Subset Construction
This approach iteratively constructs the power set by extending previously generated sets with each new number. During the process, duplicates are skipped by comparing the current number with the previous one. This ensures subsets generated in each iteration are unique.
from typing import List
def subsetsWithDup(nums: List[int]) -> List[List[int]]:
nums.sort()
result = [[]]
newSize = 0
for i in range(len(nums)):
start = newSize if i > 0 and nums[i] == nums[i - 1] else 0
newSize = len(result)
for j in range(start, newSize):
result.append(result[j] + [nums[i]])
return result
# Example Usage
result = subsetsWithDup([1, 2, 2])
for subset in result:
print(subset)import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Solution {
public List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> result = new ArrayList<>();
result.add(new ArrayList<>());
int start, newSize = 0;
for (int i = 0; i < nums.length; i++) {
start = (i > 0 && nums[i] == nums[i - 1]) ? newSize : 0;
newSize = result.size();
for (int j = start; j < newSize; j++) {
List<Integer> clone = new ArrayList<>(result.get(j));
clone.add(nums[i]);
result.add(clone);
}
}
return result;
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] nums = {1, 2, 2};
List<List<Integer>> result = solution.subsetsWithDup(nums);
for (List<Integer> subset : result) {
System.out.println(subset);
}
}
}#include <iostream>
#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 = {{}}, newSets;
size_t start = 0, newSize;
for (size_t i = 0; i < nums.size(); ++i) {
start = (i > 0 && nums[i] == nums[i - 1]) ? newSize : 0;
newSize = result.size();
newSets.clear();
for (size_t j = start; j < newSize; ++j) {
newSets.push_back(result[j]);
newSets.back().push_back(nums[i]);
}
result.insert(result.end(), newSets.begin(), newSets.end());
}
return result;
}
};
int main() {
Solution solution;
std::vector<int> nums = {1, 2, 2};
std::vector<std::vector<int>> result = solution.subsetsWithDup(nums);
for (const auto& subset : result) {
std::cout << "[";
for (size_t i = 0; i < subset.size(); ++i) {
std::cout << subset[i] << (i + 1 < subset.size() ? ", " : "");
}
std::cout << "]\n";
}
return 0;
}function subsetsWithDup(nums) {
nums.sort((a, b) => a - b);
const result = [[]];
let newSize = 0;
for (let i = 0; i < nums.length; i++) {
const start = i > 0 && nums[i] === nums[i - 1] ? newSize : 0;
newSize = result.length;
for (let j = start; j < newSize; j++) {
result.push([...result[j], nums[i]]);
}
}
return result;
}
// Example Usage
console.log(subsetsWithDup([1, 2, 2]));#include <stdio.h>
#include <stdlib.h>
int cmp(const void *a, const void *b) {
return (*(int *)a) - (*(int *)b);
}
int ** subsetsWithDup(int *nums, int numsSize, int *returnSize, int **returnColumnSizes) {
qsort(nums, numsSize, sizeof(int), cmp);
int maxNum = 1 << numsSize;
int **results = malloc(maxNum * sizeof(int *));
*returnColumnSizes = malloc(maxNum * sizeof(int));
*returnSize = 0;
results[(*returnSize)++] = malloc(0);
(*returnColumnSizes)[0] = 0;
int start, newSize;
for (int i = 0; i < numsSize; i++) {
start = (i > 0 && nums[i] == nums[i - 1]) ? newSize : 0;
newSize = *returnSize;
for (int j = start; j < newSize; j++) {
int *currentSubset = malloc(((*returnColumnSizes)[j] + 1) * sizeof(int));
for (int k = 0; k < (*returnColumnSizes)[j]; k++)
currentSubset[k] = results[j][k];
currentSubset[(*returnColumnSizes)[j]] = nums[i];
results[*returnSize] = currentSubset;
(*returnColumnSizes)[*returnSize] = (*returnColumnSizes)[j] + 1;
(*returnSize)++;
}
}
return results;
}
int main() {
int nums[] = {1,2,2};
int returnSize;
int *returnColumnSizes;
int **result = subsetsWithDup(nums, 3, &returnSize, &returnColumnSizes);
for (int i = 0; i < returnSize; i++) {
printf("[");
for (int j = 0; j < returnColumnSizes[i]; j++) {
if (j != 0) printf(", ");
printf("%d", result[i][j]);
}
printf("]\n");
free(result[i]);
}
free(result);
free(returnColumnSizes);
return 0;
}using System;
using System.Collections.Generic;
class Solution {
public IList<IList<int>> SubsetsWithDup(int[] nums) {
Array.Sort(nums);
IList<IList<int>> result = new List<IList<int>>();
result.Add(new List<int>());
int start, newSize = 0;
for (int i = 0; i < nums.Length; i++) {
start = (i > 0 && nums[i] == nums[i - 1]) ? newSize : 0;
newSize = result.Count;
for (int j = start; j < newSize; j++) {
List<int> current = new List<int>(result[j]);
current.Add(nums[i]);
result.Add(current);
}
}
return result;
}
public static void Main(string[] args) {
Solution solution = new Solution();
var result = solution.SubsetsWithDup(new int[] { 1, 2, 2 });
foreach (var subset in result) {
Console.WriteLine("[" + string.Join(", ", subset) + "]");
}
}
}The Python solution follows an iterative subset generation strategy. By sorting and managing index boundaries, duplicate subsets are avoided, efficiently constructing the complete set.
The solution involves a time complexity of O(2^n * n) for constructing the subsets and a space complexity of O(2^n * n) in terms of accumulating results progressively.
Approach 3: Sorting + DFS
We can first sort the array nums to facilitate deduplication.
Then, we design a function dfs(i), which represents the current search for subsets starting from the i-th element. The execution logic of the function dfs(i) is as follows:
If i geq n, it means all elements have been searched, add the current subset to the answer array, and end the recursion.
If i < n, add the i-th element to the subset, execute dfs(i + 1), then remove the i-th element from the subset. Next, we check if the i-th element is the same as the next element. If they are the same, skip the element in a loop until we find the first element different from the i-th element, then execute dfs(i + 1).
Finally, we only need to call dfs(0) and return the answer array.
The time complexity is O(n times 2^n), and the space complexity is O(n). Here, n is the length of the array nums.
function subsetsWithDup(nums: number[]): number[][] {
nums.sort((a, b) => a - b);
const n = nums.length;
const t: number[] = [];
const ans: number[][] = [];
const dfs = (i: number): void => {
if (i >= n) {
ans.push([...t]);
return;
}
t.push(nums[i]);
dfs(i + 1);
t.pop();
while (i + 1 < n && nums[i] === nums[i + 1]) {
i++;
}
dfs(i + 1);
};
dfs(0);
return ans;
}func subsetsWithDup(nums []int) (ans [][]int) {
slices.Sort(nums)
n := len(nums)
t := []int{}
var dfs func(int)
dfs = func(i int) {
if i >= n {
ans = append(ans, slices.Clone(t))
return
}
t = append(t, nums[i])
dfs(i + 1)
t = t[:len(t)-1]
for i+1 < n && nums[i+1] == nums[i] {
i++
}
dfs(i + 1)
}
dfs(0)
return
}impl Solution {
pub fn subsets_with_dup(nums: Vec<i32>) -> Vec<Vec<i32>> {
let mut nums = nums;
nums.sort();
let mut ans = Vec::new();
let mut t = Vec::new();
fn dfs(i: usize, nums: &Vec<i32>, t: &mut Vec<i32>, ans: &mut Vec<Vec<i32>>) {
if i >= nums.len() {
ans.push(t.clone());
return;
}
t.push(nums[i]);
dfs(i + 1, nums, t, ans);
t.pop();
let mut i = i;
while i + 1 < nums.len() && nums[i + 1] == nums[i] {
i += 1;
}
dfs(i + 1, nums, t, ans);
}
dfs(0, &nums, &mut t, &mut ans);
ans
}
}Approach 4: Sorting + Binary Enumeration
Similar to Solution 1, we first sort the array nums to facilitate deduplication.
Next, we enumerate a binary number mask in the range [0, 2^n), where the binary representation of mask is an n-bit bit string. If the i-th bit of mask is 1, it means selecting nums[i], and 0 means not selecting nums[i]. Note that if the (i - 1)-th bit of mask is 0 and nums[i] = nums[i - 1], it means that the i-th element is the same as the (i - 1)-th element in the current enumeration scheme. To avoid duplication, we skip this case. Otherwise, we add the subset corresponding to mask to the answer array.
After the enumeration, we return the answer array.
The time complexity is O(n times 2^n), and the space complexity is O(n). Here, n is the length of the array nums.
function subsetsWithDup(nums: number[]): number[][] {
nums.sort((a, b) => a - b);
const n = nums.length;
const ans: number[][] = [];
for (let mask = 0; mask < 1 << n; ++mask) {
const t: number[] = [];
let ok: boolean = true;
for (let i = 0; i < n; ++i) {
if (((mask >> i) & 1) === 1) {
if (i && ((mask >> (i - 1)) & 1) === 0 && nums[i] === nums[i - 1]) {
ok = false;
break;
}
t.push(nums[i]);
}
}
if (ok) {
ans.push(t);
}
}
return ans;
}func subsetsWithDup(nums []int) (ans [][]int) {
sort.Ints(nums)
n := len(nums)
for mask := 0; mask < 1<<n; mask++ {
t := []int{}
ok := true
for i := 0; i < n; i++ {
if mask>>i&1 == 1 {
if i > 0 && mask>>(i-1)&1 == 0 && nums[i] == nums[i-1] {
ok = false
break
}
t = append(t, nums[i])
}
}
if ok {
ans = append(ans, t)
}
}
return
}impl Solution {
pub fn subsets_with_dup(nums: Vec<i32>) -> Vec<Vec<i32>> {
let mut nums = nums;
nums.sort();
let n = nums.len();
let mut ans = Vec::new();
for mask in 0..1 << n {
let mut t = Vec::new();
let mut ok = true;
for i in 0..n {
if ((mask >> i) & 1) == 1 {
if i > 0 && ((mask >> (i - 1)) & 1) == 0 && nums[i] == nums[i - 1] {
ok = false;
break;
}
t.push(nums[i]);
}
}
if ok {
ans.push(t);
}
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Backtracking with Sorting | The time complexity is O(2^n * n), where each subset is derived and processed. The space complexity involves space for call stacks and temporary path storage, maintaining an average complexity of O(n). |
| Approach 2: Iterative Subset Construction | The solution involves a time complexity of O(2^n * n) for constructing the subsets and a space complexity of O(2^n * n) in terms of accumulating results progressively. |
| Sorting + DFS | – |
| Sorting + Binary Enumeration | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking with Sorting | O(n·2^n) | O(n) (excluding output) | Best for interviews. Clean recursion and easy duplicate skipping after sorting. |
| Iterative Subset Construction | O(n·2^n) | O(n·2^n) | Useful when avoiding recursion or when building subsets step-by-step iteratively. |
Frequently asked questions
Is Subsets II easy or hard?
Subsets II is generally considered a medium-level problem. Generating subsets alone is straightforward, but correctly handling duplicate elements adds complexity. Understanding sorting and pruning duplicate branches in backtracking is the key challenge.
How to solve Subsets II in O(n)?
Generating all subsets cannot be done in O(n) time because the output itself can contain up to 2^n subsets. Any correct algorithm must at least enumerate those subsets. The optimal practical complexity is O(n·2^n) using backtracking or iterative subset construction.
What is the best approach for Subsets II?
Backtracking with sorting is the most common solution. Sorting groups duplicate numbers together, and the recursion skips repeated values at the same depth using a simple condition. This prevents generating duplicate subsets while still exploring all valid combinations. The complexity is O(n·2^n) time with O(n) recursion stack space.
What data structure is used in Subsets II?
The main data structures are arrays or lists to store the current subset and the final result list. The algorithm also relies on sorting the array first to group duplicates. Recursion stacks or iterative lists are used to expand subsets step by step.
What is the time complexity of Subsets II?
The time complexity is O(n·2^n). A set with n elements has up to 2^n subsets, and copying each subset into the result may take O(n) time. Both the backtracking and iterative approaches have the same asymptotic complexity.
Subsets II Python or Java solution approach?
Both Python and Java implementations typically use the same backtracking strategy. Sort the array, recursively build subsets, and skip duplicates with a condition that checks if the current value equals the previous value at the same recursion level. This produces only unique subsets efficiently.
Is Subsets II asked at Google, Amazon, or Meta?
Subsets-style problems frequently appear in interviews at companies like Amazon, Google, and Meta. Variants include Subsets, Subsets II, Combination Sum, and Permutations with duplicates. Interviewers use these problems to evaluate recursion, pruning strategies, and handling duplicates.