Log inSign up
mediumLeetCodeNot Started

Subsets II

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Backtracking
Solve on LeetCode
Lesson

Problem Statement

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]]
Explanation: Contains all 6 distinct unique subsets without duplicates.

Example 2:

Input: nums = [0]
Output: [[],[0]]
Explanation: The 2 subsets of [0].

Constraints:

  • 1 <= nums.length <= 10
  • -10 <= nums[i] <= 10

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the i > start sibling deduplication idiom used in combination and subset backtracking.
  • Understand why i > start allows vertical duplicate inclusion ([2, 2]) while disallowing horizontal duplicate branching.
  • Apply duplicate handling across different paradigms (recursive DFS vs iterative cascading).

1. Bitmask Generation + Hash Set Deduplication

Intuition

Sort nums initially so subsets have consistent canonical order. Iterate mask from 0 to 2N - 1, build subset, serialize to string or set to deduplicate.

Algorithm

  1. Step 1: Sort each generated subset and insert into a Hash Set of lists.
  2. Step 2: Explore all 2N subsets using standard backtracking.
  3. Step 3: Convert the unique set of subsets into the final result list.
  4. Step 4: Return result.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <set>
4#include <algorithm>
5
6class Solution {
7public:
8 std::vector<std::vector<int>> subsetsWithDup(std::vector<int>& nums) {
9 std::sort(nums.begin(), nums.end());
10 int n = nums.size();
11 int total = 1 << n;
12 std::set<std::vector<int>> uniqueSubsets;
13
14 for (int mask = 0; mask < total; mask++) {
15 std::vector<int> current;
16 for (int j = 0; j < n; j++) {
17 if ((mask >> j) & 1) {
18 current.push_back(nums[j]);
19 }
20 }
21 uniqueSubsets.insert(current);
22 }
23 return std::vector<std::vector<int>>(uniqueSubsets.begin(), uniqueSubsets.end());
24 }
25};
26
27int main() {
28 Solution solver;
29 std::vector<int> nums = {1, 2, 2};
30 std::vector<std::vector<int>> res = solver.subsetsWithDup(nums);
31 std::cout << "Brute Force Subsets for [1, 2, 2]:\n";
32 for (const auto& s : res) {
33 std::cout << "[ ";
34 for (int x : s) std::cout << x << " ";
35 std::cout << "]\n";
36 }
37 return 0;
38}

Time & Space Complexity

  • Time complexity: O(N * 2^N) — Generates all 2N subsets and hashes each.
  • Space complexity: O(N * 2^N) — Hash Set stores up to 2N subsets.

2. Iterative Cascading with Duplicate Index Tracking

Intuition

Maintain startIndex = 0. If nums[i] == nums[i-1], set startIndex = previousSize instead of 0. This guarantees identical elements are appended only once per subset length.

Algorithm

  1. Step 1: Sort nums array in non-decreasing order upfront.
  2. Step 2: When encountering duplicate numbers, only add them to subsets created in the previous step.
  3. Step 3: Maintain startIndex and endIndex pointers during iterative cascade.
  4. Step 4: Append new subsets to result.
  5. Step 5: Return result.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5class Solution {
6public:
7 std::vector<std::vector<int>> subsetsWithDup(std::vector<int>& nums) {
8 std::sort(nums.begin(), nums.end());
9 std::vector<std::vector<int>> result = {{}};
10 int startIndex = 0, endIndex = 0;
11
12 for (int i = 0; i < (int)nums.size(); i++) {
13 startIndex = 0;
14 if (i > 0 && nums[i] == nums[i - 1]) {
15 startIndex = endIndex + 1;
16 }
17 endIndex = result.size() - 1;
18 int n = result.size();
19 for (int j = startIndex; j < n; j++) {
20 std::vector<int> newSub = result[j];
21 newSub.push_back(nums[i]);
22 result.push_back(newSub);
23 }
24 }
25 return result;
26 }
27};
28
29int main() {
30 Solution solver;
31 std::vector<int> nums = {1, 2, 2};
32 std::vector<std::vector<int>> res = solver.subsetsWithDup(nums);
33 std::cout << "Cascading Subsets for [1, 2, 2]:\n";
34 for (const auto& s : res) {
35 std::cout << "[ ";
36 for (int x : s) std::cout << x << " ";
37 std::cout << "]\n";
38 }
39 return 0;
40}

Time & Space Complexity

  • Time complexity: O(N * 2^N) — Directly creates only unique subsets without duplicates.
  • Space complexity: O(1) auxiliary space — No recursion stack.

3. Sort + Backtracking Sibling Pruning (Gold Standard)

Intuition

Sorting puts duplicates adjacent. If i > start && nums[i] == nums[i - 1], nums[i] is a sibling node that would explore the exact same subset choices as nums[i-1]. Pruning this sibling branch generates strictly unique subsets with zero overhead.

Algorithm

  1. Step 1: Sort nums array in ascending order upfront: O(N log N).
  2. Step 2: In backtrack(start, current): add a copy of current to result list.
  3. Step 3: Loop i from start to nums.length - 1.
  4. Step 4: Duplicate pruning check: if i > start && nums[i] == nums[i-1], continue (skip duplicate branch).
  5. Step 5: Push nums[i] to current, recurse on backtrack(i + 1, current), then pop.
  6. Step 6: Return result containing only unique subsets.

Duplicate-Skipping Subset Trace

2 of 2 questions left today
Step 1 / 5
Trace timeline20% explored
Current operationSTEP 1 OF 5
Sort nums to [1, 2, 2]
Visual state
Values and pointers at this exact step
tree
Root
[]

Node order shown; add connections to display explicit tree edges.

Variables at this step
current
[]
count
1
Check / comparison
nums = [1, 2, 2] (sorted), current = []
Decision / next transition
Record [] (Subset 1)
Why this step matters

Sort nums to [1, 2, 2]. Start at root with current = []. Add [] to result.

Step 1 / 5
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5class Solution {
6public:
7 void backtrack(int start, std::vector<int>& nums, std::vector<int>& path, std::vector<std::vector<int>>& result) {
8 result.push_back(path);
9 for (int i = start; i < (int)nums.size(); i++) {
10 // Prune duplicate sibling branch
11 if (i > start && nums[i] == nums[i - 1]) continue;
12
13 path.push_back(nums[i]);
14 backtrack(i + 1, nums, path, result);
15 path.pop_back();
16 }
17 }
18
19 std::vector<std::vector<int>> subsetsWithDup(std::vector<int>& nums) {
20 std::sort(nums.begin(), nums.end());
21 std::vector<std::vector<int>> result;
22 std::vector<int> path;
23 backtrack(0, nums, path, result);
24 return result;
25 }
26};
27
28int main() {
29 Solution solver;
30 std::vector<int> nums = {1, 2, 2};
31 std::vector<std::vector<int>> res = solver.subsetsWithDup(nums);
32 std::cout << "Optimal Subsets with Dup for [1, 2, 2]:\n";
33 for (const auto& s : res) {
34 std::cout << "[ ";
35 for (int x : s) std::cout << x << " ";
36 std::cout << "]\n";
37 }
38 return 0;
39}

Time & Space Complexity

  • Time complexity: O(N * 2^N) — Generates exactly the unique power set size multiplied by O(N) path snapshot cost.
  • Space complexity: O(N) — O(N) recursion stack memory.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Generate All Subsets + Set DeduplicationO(N * 2^N)O(N * 2^N)Generate all 2N subsets, sort each subset, and insert into a Hash Set.Set hashing and allocations
2.Iterative Cascading with Duplicate Index TrackingO(N * 2^N)O(1)When encounter duplicate nums[i], only append nums[i] to subsets created in the previous step.Array slicing and cloning
3.Sort + Backtracking Sibling Pruning (Optimal)OptimalO(N * 2^N)O(N)Sort array and skip sibling duplicates i > start && nums[i] == nums[i - 1] during recursion.Path cloning at nodes

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Writing if (i > 0 && nums[i] == nums[i-1]) instead of i > start. This incorrectly skips valid duplicate choices down the vertical tree path.

Pitfall 2:

Forgetting to sort the array before backtracking.

Crucial Edge Cases to Validate:

  • Array with all duplicate elements (e.g. [2, 2, 2]) -> returns [[], [2], [2, 2], [2, 2, 2]] (N + 1 subsets).
  • Array with all unique elements (e.g. [1, 2, 3]) -> returns standard 2N = 8 subsets.
  • Single element (e.g. [0]) -> returns [[], [0]].

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Clearly articulate why i > start works for combinations/subsets whereas !used[i-1] is used for permutations.
  2. Showcase both the recursive backtracking solution and the iterative cascading solution to impress the interviewer.
  3. Calculate the output size: if an array contains duplicates with frequencies c1, c2, ..., ck, the total number of unique subsets is (c1 + 1) * (c2 + 1) * ... * (ck + 1).

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why is i > start used in i > start && nums[i] == nums[i-1]?

Back to DSA Sheet