Log inSign up
mediumLeetCodeNot Started

Subsets

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

Backtracking
Solve on LeetCode
Lesson

Problem Statement

Given an integer array nums of unique elements, 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,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
Explanation: The 23 = 8 subsets of [1, 2, 3] in any valid permutation.

Example 2:

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

Constraints:

  • 1 <= nums.length <= 10
  • -10 <= nums[i] <= 10
  • All the numbers of nums are unique.

What You'll Learn

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

  • Master the standard backtracking loop template for combinations and subsets.
  • Understand the equivalence between the binary power set and integer bitmask representations.
  • Recognize how subset problems form the foundation for 0/1 knapsack and NP-complete search.

1. Bitmask Power Set Enumeration

Intuition

Since every element can independently be either present (1) or absent (0), there are exactly 2N subsets corresponding to the binary representation of integers from 0 to 2N - 1.

Algorithm

  1. Step 1: Start with result list containing the empty subset [].
  2. Step 2: For each number in nums, iterate through all existing subsets in result.
  3. Step 3: Create a new subset by adding the current number to each existing subset.
  4. Step 4: Append all newly created subsets back into result.
  5. Step 5: Return result containing 2N subsets.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4class Solution {
5public:
6 std::vector<std::vector<int>> subsets(std::vector<int>& nums) {
7 int n = nums.size();
8 int totalSubsets = 1 << n;
9 std::vector<std::vector<int>> result;
10 result.reserve(totalSubsets);
11
12 for (int mask = 0; mask < totalSubsets; mask++) {
13 std::vector<int> current;
14 for (int j = 0; j < n; j++) {
15 if ((mask >> j) & 1) {
16 current.push_back(nums[j]);
17 }
18 }
19 result.push_back(current);
20 }
21 return result;
22 }
23};
24
25int main() {
26 Solution solver;
27 std::vector<int> nums = {1, 2, 3};
28 std::vector<std::vector<int>> res = solver.subsets(nums);
29 std::cout << "Bitmask Subsets for [1, 2, 3]:\n";
30 for (const auto& sub : res) {
31 std::cout << "[ ";
32 for (int x : sub) std::cout << x << " ";
33 std::cout << "]\n";
34 }
35 return 0;
36}

Time & Space Complexity

  • Time complexity: O(N * 2^N) — Total of 2N numbers checked, with N bit checks each.
  • Space complexity: O(1) auxiliary space (excluding output) — Requires no recursive stack or temporary buffer beyond the current subset.

2. Cascading Iteration

Intuition

Iteratively build the power set. With nums = [1, 2, 3]: start [[]]. After 1: [[], [1]]. After 2: [[], [1], [2], [1, 2]]. After 3: doubles to 8 subsets.

Algorithm

  1. Step 1: Notice that an array of length N has exactly 2N subsets, corresponding to binary numbers 0 to (2N - 1).
  2. Step 2: Loop mask from 0 to (1 << n) - 1.
  3. Step 3: For each bit position i from 0 to n - 1, if ((mask >> i) & 1) == 1, include nums[i].
  4. Step 4: Add the constructed subset to result list.
  5. Step 5: Return result.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4class Solution {
5public:
6 std::vector<std::vector<int>> subsets(std::vector<int>& nums) {
7 std::vector<std::vector<int>> result = {{}};
8 for (int num : nums) {
9 int currentSize = result.size();
10 for (int i = 0; i < currentSize; i++) {
11 std::vector<int> newSubset = result[i];
12 newSubset.push_back(num);
13 result.push_back(newSubset);
14 }
15 }
16 return result;
17 }
18};
19
20int main() {
21 Solution solver;
22 std::vector<int> nums = {1, 2, 3};
23 std::vector<std::vector<int>> res = solver.subsets(nums);
24 std::cout << "Cascading Subsets for [1, 2, 3]:\n";
25 for (const auto& sub : res) {
26 std::cout << "[ ";
27 for (int x : sub) std::cout << x << " ";
28 std::cout << "]\n";
29 }
30 return 0;
31}

Time & Space Complexity

  • Time complexity: O(N * 2^N) — At step i, doubles the number of subsets from 2^(i-1) to 2i.
  • Space complexity: O(1) auxiliary space — Builds output directly without extra recursion or helper containers.

3. Backtracking with Start Index (Gold Standard)

Intuition

At every state, result.push_back(path). Loop i from start to nums.size() - 1, append nums[i] to path, recurse with start = i + 1, and pop nums[i] on backtrack. This traverses a standard combination tree where each node is a distinct subset.

Algorithm

  1. Step 1: Define backtrack(start, current).
  2. Step 2: Add a copy of current to result list at every node in the recursion tree.
  3. Step 3: Loop i from start to nums.length - 1.
  4. Step 4: Push nums[i] to current.
  5. Step 5: Recurse on backtrack(i + 1, current).
  6. Step 6: Backtrack: pop nums[i] from current.
  7. Step 7: Return result containing all 2N subsets.

Subsets Decision Tree Trace

2 of 2 questions left today
Step 1 / 5
Trace timeline20% explored
Current operationSTEP 1 OF 5
Start at root with current = []
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
[]
totalSubsets
1
Check / comparison
current = [], add to result
Decision / next transition
Record [] (Subset 1/8)
Why this step matters

Start at root with current = []. Add [] to result.

Step 1 / 5
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4class Solution {
5public:
6 void backtrack(int start, std::vector<int>& nums, std::vector<int>& path, std::vector<std::vector<int>>& result) {
7 result.push_back(path);
8 for (int i = start; i < (int)nums.size(); i++) {
9 path.push_back(nums[i]);
10 backtrack(i + 1, nums, path, result);
11 path.pop_back();
12 }
13 }
14
15 std::vector<std::vector<int>> subsets(std::vector<int>& nums) {
16 std::vector<std::vector<int>> result;
17 std::vector<int> path;
18 backtrack(0, nums, path, result);
19 return result;
20 }
21};
22
23int main() {
24 Solution solver;
25 std::vector<int> nums = {1, 2, 3};
26 std::vector<std::vector<int>> res = solver.subsets(nums);
27 std::cout << "Backtracking Subsets for [1, 2, 3]:\n";
28 for (const auto& sub : res) {
29 std::cout << "[ ";
30 for (int x : sub) std::cout << x << " ";
31 std::cout << "]\n";
32 }
33 return 0;
34}

Time & Space Complexity

  • Time complexity: O(N * 2^N) — Visits exactly 2N recursion tree nodes, copying path of size up to N at each node.
  • Space complexity: O(N) — Recursion depth is bounded by N.

Approach Comparison Matrix

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

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Bitmask EnumerationO(N * 2^N)O(1)Map each integer mask from 0 to 2N - 1 to a unique binary subset selection.Bit testing loop
2.Cascading IterationO(N * 2^N)O(1)Start with empty subset [[]]. For each num, duplicate all existing subsets and append num.Array cloning
3.Backtracking (DFS with Start Index)OptimalO(N * 2^N)O(N)Traverse combinatorial recursion tree, appending path snapshot at each node.Deep recursion copying

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Appending the reference to path instead of creating a deep copy (new ArrayList<>(path) / [...path]).

Pitfall 2:

Passing start + 1 instead of i + 1 to the recursive call, causing infinite loops or duplicate indices.

Crucial Edge Cases to Validate:

  • Single element (nums = [0]) -> returns [[], [0]].
  • Empty array -> returns [[]].
  • Negative numbers (nums = [-1, 2]) -> handled cleanly without special casing.

Interview Tips & Best Practices

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

  1. Mention both Backtracking DFS and Bitmasking to demonstrate versatility across problem paradigms.
  2. Highlight that cloning the path takes O(N) time at each of the 2N nodes, making the total complexity O(N * 2N).
  3. Seamlessly lead into Subsets II (handling duplicates) by discussing how sorting enables adjacent duplicate pruning.

Quick Comprehension Check

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

1.Why does passing i + 1 to the recursive backtrack call prevent duplicate subsets and self-selections?

Back to DSA Sheet