Subsets

🎯

Subsets

mediumBACKTRACKINGAmazonFacebookGoogle

Imagine you have a set of unique ingredients and want to explore every possible combination to create new recipes.

💡 This problem asks for all possible subsets of a set. Beginners often struggle because the number of subsets grows exponentially and the recursive include/exclude pattern can be tricky to grasp initially.

📋

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.

1 ≤ nums.length ≤ 20-10^6 ≤ nums[i] ≤ 10^6All elements of nums are unique

💡

Example

Input"[1,2,3]"

Output[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

Starting from empty set, we either include or exclude each element, generating all subsets.

• Empty input array → output [[]]
• Single element array → output [[], [element]]
• All elements are negative → subsets still valid
• Large input size (e.g., 20 elements) → ensure no stack overflow or timeout

⚠️

Common Mistakes

Not copying the current subset before adding to result

All subsets in result end up being the same final list due to mutation

✅ Append a copy (e.g., path[:] in Python) instead of the reference

Forgetting to backtrack (pop) after including an element

Subsets accumulate extra elements, producing incorrect subsets

✅ Always remove the last element after recursive call to restore state

Using global variables without resetting between test cases

Results from previous runs contaminate current output

✅ Initialize result inside the function or clear it before use

Misunderstanding base case leading to missing empty subset

Empty subset is not included in final output

✅ Ensure base case adds current path even if empty

Using iterative approach without handling empty subset

Empty subset might be missed if loop starts incorrectly

✅ Start from mask = 0 to include empty subset

🧠

Brute Force (Pure Recursion Include/Exclude)

💡 This approach is the foundation for understanding subsets generation. It explicitly explores every possibility by deciding to include or exclude each element, which helps grasp the recursion tree structure.

Intuition

At each element, we have two choices: include it in the current subset or exclude it. Recursively applying this for all elements generates all subsets.

Algorithm

1. Start from the first element and an empty current subset.
2. At each step, recursively explore two paths: one including the current element, one excluding it.
3. When all elements are processed, add the current subset to the result.
4. Return the collected subsets after exploring all branches.

💡 The challenge is to visualize the recursion tree and understand how subsets accumulate at the leaves.

</>

Code

from typing import List

def subsets(nums: List[int]) -> List[List[int]]:
    result = []
    def backtrack(index: int, path: List[int]):
        if index == len(nums):
            result.append(path[:])
            return
        # Exclude current element
        backtrack(index + 1, path)
        # Include current element
        path.append(nums[index])
        backtrack(index + 1, path)
        path.pop()
    backtrack(0, [])
    return result

# Driver code
if __name__ == '__main__':
    print(subsets([1,2,3]))

Line Notes

def subsets(nums: List[int]) -> List[List[int]]:Defines the main function with type hints for clarity

result = []Stores all subsets generated during recursion

def backtrack(index: int, path: List[int]):Helper recursive function tracking current index and current subset path

if index == len(nums):Base case: all elements processed, add current subset to result

result.append(path[:])Append a copy of current subset to avoid mutation issues

backtrack(index + 1, path)Explore path including the current element

path.append(nums[index])Include current element before next recursion

path.pop()Backtrack by removing last element to restore state

import java.util.*;

public class Subsets {
    public static List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(nums, 0, new ArrayList<>(), result);
        return result;
    }

    private static void backtrack(int[] nums, int index, List<Integer> path, List<List<Integer>> result) {
        if (index == nums.length) {
            result.add(new ArrayList<>(path));
            return;
        }
        // Exclude current element
        backtrack(nums, index + 1, path, result);
        // Include current element
        path.add(nums[index]);
        backtrack(nums, index + 1, path, result);
        path.remove(path.size() - 1);
    }

    public static void main(String[] args) {
        System.out.println(subsets(new int[]{1,2,3}));
    }
}

Line Notes

public static List<List<Integer>> subsets(int[] nums)Main function signature returning list of subsets

List<List<Integer>> result = new ArrayList<>();Stores all subsets generated

backtrack(nums, 0, new ArrayList<>(), result);Start recursion from index 0 with empty path

if (index == nums.length)Base case: all elements processed, add current subset

result.add(new ArrayList<>(path));Add a copy of current subset to result

backtrack(nums, index + 1, path, result);Explore path including the current element

path.add(nums[index]);Include current element before recursion

path.remove(path.size() - 1);Backtrack to restore path state

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    void backtrack(vector<int>& nums, int index, vector<int>& path, vector<vector<int>>& result) {
        if (index == nums.size()) {
            result.push_back(path);
            return;
        }
        // Exclude current element
        backtrack(nums, index + 1, path, result);
        // Include current element
        path.push_back(nums[index]);
        backtrack(nums, index + 1, path, result);
        path.pop_back();
    }

    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> result;
        vector<int> path;
        backtrack(nums, 0, path, result);
        return result;
    }
};

int main() {
    Solution sol;
    vector<int> nums = {1,2,3};
    vector<vector<int>> res = sol.subsets(nums);
    for (auto &subset : res) {
        cout << "[";
        for (int i = 0; i < subset.size(); i++) {
            cout << subset[i];
            if (i != subset.size() - 1) cout << ",";
        }
        cout << "] ";
    }
    cout << endl;
    return 0;
}

Line Notes

void backtrack(vector<int>& nums, int index, vector<int>& path, vector<vector<int>>& result)Recursive helper with current index and subset path

if (index == nums.size())Base case: all elements processed, add current subset

result.push_back(path);Add current subset to result vector

backtrack(nums, index + 1, path, result);Explore path including the current element

path.push_back(nums[index]);Include current element before recursion

path.pop_back();Backtrack to restore path state

int main()Driver code to test the subsets function

function subsets(nums) {
    const result = [];
    function backtrack(index, path) {
        if (index === nums.length) {
            result.push([...path]);
            return;
        }
        // Exclude current element
        backtrack(index + 1, path);
        // Include current element
        path.push(nums[index]);
        backtrack(index + 1, path);
        path.pop();
    }
    backtrack(0, []);
    return result;
}

// Test
console.log(subsets([1,2,3]));

Line Notes

function subsets(nums) {Defines main function to generate subsets

const result = [];Stores all subsets generated

function backtrack(index, path) {Recursive helper tracking index and current subset

if (index === nums.length) {Base case: all elements processed, add current subset

result.push([...path]);Add a copy of current subset to result

backtrack(index + 1, path);Explore path including the current element

path.push(nums[index]);Include current element before recursion

path.pop();Backtrack to restore path state

⏱

Complexity

TimeO(2^n * n)

SpaceO(n) recursion stack + O(2^n * n) output

Each element has two choices, leading to 2^n subsets. Copying each subset of average length n leads to O(2^n * n) time and space.

💡 For n=20, 2^20 is about 1 million subsets, so this approach is feasible but can be slow for larger n.

Interview Verdict: Accepted

Though exponential, this brute force approach is the standard solution for generating all subsets and is accepted for typical input sizes.

🧠

Backtracking with For-Loop (Iterative Choice at Each Level)

💡 This approach uses backtracking with a for-loop to build subsets incrementally, which is often easier to understand and implement than pure include/exclude recursion.

Intuition

Instead of binary decisions at each element, we choose the next element to add from the remaining elements, building subsets step-by-step.

Algorithm

1. Start with an empty subset and add it to the result.
2. Iterate over elements starting from current index.
3. Add the current element to the subset and recurse to add further elements.
4. Backtrack by removing the last element and continue iteration.

💡 This approach is easier to visualize as building subsets by growing them one element at a time.

</>

Code

from typing import List

def subsets(nums: List[int]) -> List[List[int]]:
    result = []
    def backtrack(start: int, path: List[int]):
        result.append(path[:])
        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i + 1, path)
            path.pop()
    backtrack(0, [])
    return result

# Driver code
if __name__ == '__main__':
    print(subsets([1,2,3]))

Line Notes

def subsets(nums: List[int]) -> List[List[int]]:Defines main function with type hints

result = []Stores all subsets generated

def backtrack(start: int, path: List[int]):Helper recursive function with start index and current subset

result.append(path[:])Add current subset to result at each recursion level

for i in range(start, len(nums))Iterate over remaining elements to add

path.append(nums[i])Include current element before recursion

backtrack(i + 1, path)Recurse with next start index

path.pop()Backtrack to restore path state

import java.util.*;

public class Subsets {
    public static List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(nums, 0, new ArrayList<>(), result);
        return result;
    }

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

    public static void main(String[] args) {
        System.out.println(subsets(new int[]{1,2,3}));
    }
}

Line Notes

public static List<List<Integer>> subsets(int[] nums)Main function signature

List<List<Integer>> result = new ArrayList<>();Stores all subsets

backtrack(nums, 0, new ArrayList<>(), result);Start recursion from index 0

result.add(new ArrayList<>(path));Add current subset at each recursion level

for (int i = start; i < nums.length; i++)Iterate over remaining elements

path.add(nums[i]);Include current element

backtrack(nums, i + 1, path, result);Recurse with next start index

path.remove(path.size() - 1);Backtrack to restore path

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    void backtrack(vector<int>& nums, int start, vector<int>& path, vector<vector<int>>& result) {
        result.push_back(path);
        for (int i = start; i < nums.size(); i++) {
            path.push_back(nums[i]);
            backtrack(nums, i + 1, path, result);
            path.pop_back();
        }
    }

    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> result;
        vector<int> path;
        backtrack(nums, 0, path, result);
        return result;
    }
};

int main() {
    Solution sol;
    vector<int> nums = {1,2,3};
    vector<vector<int>> res = sol.subsets(nums);
    for (auto &subset : res) {
        cout << "[";
        for (int i = 0; i < subset.size(); i++) {
            cout << subset[i];
            if (i != subset.size() - 1) cout << ",";
        }
        cout << "] ";
    }
    cout << endl;
    return 0;
}

Line Notes

void backtrack(vector<int>& nums, int start, vector<int>& path, vector<vector<int>>& result)Recursive helper with start index and current subset

result.push_back(path);Add current subset at each recursion level

for (int i = start; i < nums.size(); i++)Iterate over remaining elements

path.push_back(nums[i]);Include current element

backtrack(nums, i + 1, path, result);Recurse with next start index

path.pop_back();Backtrack to restore path

int main()Driver code to test subsets

function subsets(nums) {
    const result = [];
    function backtrack(start, path) {
        result.push([...path]);
        for (let i = start; i < nums.length; i++) {
            path.push(nums[i]);
            backtrack(i + 1, path);
            path.pop();
        }
    }
    backtrack(0, []);
    return result;
}

// Test
console.log(subsets([1,2,3]));

Line Notes

function subsets(nums) {Defines main function

const result = [];Stores all subsets

function backtrack(start, path) {Recursive helper with start index and current subset

result.push([...path]);Add current subset at each recursion level

for (let i = start; i < nums.length; i++) {Iterate over remaining elements

path.push(nums[i]);Include current element

backtrack(i + 1, path);Recurse with next start index

path.pop();Backtrack to restore path

⏱

Complexity

TimeO(2^n * n)

SpaceO(n) recursion stack + O(2^n * n) output

We generate all subsets (2^n), and copying each subset of average length n leads to O(2^n * n) time and space.

💡 This approach is often easier to implement and understand than pure include/exclude recursion.

Interview Verdict: Accepted

This approach is widely used in interviews due to its clarity and efficiency for subset generation.

🧠

Iterative Subset Generation (Bit Manipulation)

💡 This approach uses bit manipulation to generate subsets iteratively, which is efficient and avoids recursion, but requires understanding binary representations.

Intuition

Each subset corresponds to a binary number where each bit indicates whether an element is included or not.

Algorithm

1. Calculate total subsets as 2^n.
2. For each number from 0 to 2^n - 1, interpret bits as inclusion flags.
3. Build subset by including elements where corresponding bit is set.
4. Add each built subset to the result.

💡 This approach avoids recursion and directly maps subsets to binary numbers.

</>

Code

from typing import List

def subsets(nums: List[int]) -> List[List[int]]:
    n = len(nums)
    result = []
    for mask in range(1 << n):
        subset = []
        for i in range(n):
            if mask & (1 << i):
                subset.append(nums[i])
        result.append(subset)
    return result

# Driver code
if __name__ == '__main__':
    print(subsets([1,2,3]))

Line Notes

n = len(nums)Store length of input array

for mask in range(1 << n):Iterate over all binary masks from 0 to 2^n - 1

subset = []Initialize current subset for this mask

for i in range(n):Check each bit position

if mask & (1 << i):If bit i is set, include nums[i]

subset.append(nums[i])Add element to current subset

result.append(subset)Add current subset to result

import java.util.*;

public class Subsets {
    public static List<List<Integer>> subsets(int[] nums) {
        int n = nums.length;
        List<List<Integer>> result = new ArrayList<>();
        int total = 1 << n;
        for (int mask = 0; mask < total; mask++) {
            List<Integer> subset = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) != 0) {
                    subset.add(nums[i]);
                }
            }
            result.add(subset);
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println(subsets(new int[]{1,2,3}));
    }
}

Line Notes

int n = nums.length;Store length of input array

int total = 1 << n;Calculate total subsets as 2^n

for (int mask = 0; mask < total; mask++) {Iterate over all binary masks

List<Integer> subset = new ArrayList<>();Initialize current subset

if ((mask & (1 << i)) != 0)Check if bit i is set in mask

subset.add(nums[i]);Include element if bit set

result.add(subset);Add subset to result

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> result;
        int total = 1 << n;
        for (int mask = 0; mask < total; mask++) {
            vector<int> subset;
            for (int i = 0; i < n; i++) {
                if (mask & (1 << i)) {
                    subset.push_back(nums[i]);
                }
            }
            result.push_back(subset);
        }
        return result;
    }
};

int main() {
    Solution sol;
    vector<int> nums = {1,2,3};
    vector<vector<int>> res = sol.subsets(nums);
    for (auto &subset : res) {
        cout << "[";
        for (int i = 0; i < subset.size(); i++) {
            cout << subset[i];
            if (i != subset.size() - 1) cout << ",";
        }
        cout << "] ";
    }
    cout << endl;
    return 0;
}

Line Notes

int n = nums.size();Store length of input array

int total = 1 << n;Calculate total subsets as 2^n

for (int mask = 0; mask < total; mask++) {Iterate over all binary masks

vector<int> subset;Initialize current subset

if (mask & (1 << i)) {Check if bit i is set in mask

subset.push_back(nums[i]);Include element if bit set

result.push_back(subset);Add subset to result

function subsets(nums) {
    const n = nums.length;
    const result = [];
    const total = 1 << n;
    for (let mask = 0; mask < total; mask++) {
        const subset = [];
        for (let i = 0; i < n; i++) {
            if ((mask & (1 << i)) !== 0) {
                subset.push(nums[i]);
            }
        }
        result.push(subset);
    }
    return result;
}

// Test
console.log(subsets([1,2,3]));

Line Notes

const n = nums.length;Store length of input array

const total = 1 << n;Calculate total subsets as 2^n

for (let mask = 0; mask < total; mask++) {Iterate over all binary masks

const subset = [];Initialize current subset

if ((mask & (1 << i)) !== 0) {Check if bit i is set in mask

subset.push(nums[i]);Include element if bit set

result.push(subset);Add subset to result

⏱

Complexity

TimeO(2^n * n)

SpaceO(2^n * n) output + O(1) auxiliary

We generate 2^n subsets, each requiring up to n operations to build, so total time is O(2^n * n). Space is dominated by output storage.

💡 This approach is iterative and avoids recursion stack overhead, useful for languages with limited recursion depth.

Interview Verdict: Accepted

Bit manipulation is a neat trick to generate subsets efficiently and is often appreciated in interviews.

📊

All Approaches - One-Glance Tradeoffs

💡 For most interviews, the backtracking with for-loop approach is recommended due to clarity and ease of implementation.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (Include/Exclude Recursion)	O(2^n * n)	O(n) recursion + O(2^n * n) output	Yes (deep recursion for large n)	Yes	Good to mention and understand; coding is straightforward but can be verbose
2. Backtracking with For-Loop	O(2^n * n)	O(n) recursion + O(2^n * n) output	Yes (deep recursion for large n)	Yes	Preferred approach to code in interviews for clarity and efficiency
3. Iterative Bit Manipulation	O(2^n * n)	O(2^n * n) output + O(1) auxiliary	No	Yes	Good to mention as an optimization or alternative; less intuitive for beginners

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before your interview. Start by clarifying the problem, then explain the brute force approach, and finally discuss optimizations or alternative methods.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Describe the brute force include/exclude recursion approach.Step 3: Implement the brute force solution carefully.Step 4: Discuss the backtracking with for-loop approach as an alternative.Step 5: Mention the bit manipulation iterative approach if time permits.Step 6: Test your code with edge cases and explain complexity.

Time Allocation

Clarify: 2min → Approach: 3min → Code: 10min → Test: 5min. Total ~20min

What the Interviewer Tests

The interviewer tests your understanding of recursion, backtracking, and subset generation. They also assess your ability to optimize and explain your approach clearly.

Common Follow-ups

• How to handle duplicates in input? → Use sorting and skip duplicates during recursion.
• Can you generate subsets of a fixed size k? → Modify recursion to track subset size and only add when size == k.

💡 These follow-ups test your ability to adapt the base solution to common variations and constraints.

🔍

Pattern Recognition

When to Use

1) Asked to generate all subsets or power set; 2) Input is a set or array of unique elements; 3) Need all combinations without duplicates; 4) No constraints on subset size.

Signature Phrases

all possible subsetspower setreturn all combinations

NOT This Pattern When

Problems asking for subsets with sum constraints or permutations with order are related but require different approaches.

Similar Problems

Subsets II - handles duplicates by skipping repeated elementsCombination Sum - subsets with sum constraintsPermutations - order matters, unlike subsets

Practice

1. Consider the following code snippet that generates all combinations of size k from numbers 1 to n using an iterative lexicographic approach. What is the final output of combine(4, 2)?

easy

A. [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]

B. [[1, 2], [2, 3], [3, 4]]

C. [[1, 2], [1, 3], [2, 3], [2, 4], [3, 4]]

D. [[1, 2], [1, 3], [1, 4], [2, 3], [3, 4]]

Solution

1. Step 1: Trace initial combination and increments

   Start with [1, 2], then increment last element until max, then increment previous and reset subsequent.

2. Step 2: Enumerate all combinations of size 2 from 1 to 4 in lex order

   All pairs: [1,2], [1,3], [1,4], [2,3], [2,4], [3,4] are generated.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Output matches all 6 combinations of 4 choose 2 [OK]

Hint: Lexicographic iteration generates all combinations in sorted order [OK]

Common Mistakes:

• Missing some combinations due to off-by-one in increments

2. You are given a string containing letters and digits. You need to generate all possible strings by toggling the case of each letter independently, while digits remain unchanged. Which algorithmic approach guarantees generating all valid permutations efficiently?

easy

A. Backtracking with include/exclude choices for each letter's case

B. Sorting the string and then generating permutations by swapping adjacent characters

C. Dynamic programming using a bottom-up table to store partial permutations

D. Greedy algorithm that toggles letters only when it reduces the lexicographical order

Solution

1. Step 1: Understand problem constraints

   The problem requires exploring all combinations of letter cases, which is a classic subsets problem where each letter can be included as lowercase or uppercase.

2. Step 2: Identify suitable algorithm

   Backtracking with include/exclude choices for each letter's case systematically explores all 2^k combinations, ensuring completeness and correctness.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Backtracking explores all subsets of letter cases [OK]

Hint: Toggle letter cases via backtracking subsets [OK]

Common Mistakes:

• Thinking greedy can find all permutations
• Using DP that doesn't fit subsets pattern

3. You are given a set of sticks with various lengths. The goal is to determine if these sticks can be arranged to form a perfect square, using all sticks exactly once. Which algorithmic approach is most suitable to guarantee an optimal solution for this problem?

easy

A. Backtracking with bitmasking and memoization to explore all subsets efficiently while pruning invalid paths.

B. Greedy algorithm that always picks the longest stick first and tries to form sides sequentially.

C. Dynamic programming based on subset sums without pruning or memoization.

D. Simple brute force recursion that tries all possible assignments of sticks to sides without optimization.

Solution

1. Step 1: Understand problem constraints

   The problem requires using all sticks exactly once to form four equal sides, which is a partitioning problem with strict constraints.

2. Step 2: Identify suitable algorithm

   Greedy approaches fail because local choices don't guarantee global feasibility. Simple brute force is correct but inefficient. DP without pruning is too slow. Backtracking with bitmask and memoization efficiently explores subsets and prunes invalid paths, guaranteeing optimality.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Bitmask + memoization prunes repeated states [OK]

Hint: Bitmask + memoization prunes repeated states [OK]

Common Mistakes:

• Assuming greedy always works for partitioning
• Confusing DP without pruning as efficient
• Ignoring memoization benefits

4. What is the time complexity of the iterative lexicographic combinations generation algorithm for generating all combinations of size k from n elements?

medium

A. O(n^k) because each element can be chosen or not

B. O(k * (n choose k)) since each combination of size k is generated once and updated in O(k)

C. O(\u03C3(n choose k) * k) where \u03C3 is the number of combinations generated

D. O(n * k) because the outer loop runs n times and inner loop k times

Solution

1. Step 1: Identify number of combinations

   There are exactly (n choose k) combinations to generate.

2. Step 2: Analyze per-combination cost

   Each combination is generated and updated in O(k) time due to copying and resetting elements.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Time is proportional to number of combinations times combination size [OK]

Hint: Time depends on number of combinations times k [OK]

Common Mistakes:

• Confusing with exponential O(n^k) or linear O(n*k) complexities

5. What is the time complexity of the optimal bitmask + trie solution for the Number of Valid Words for Each Puzzle problem, given W words with average length L, and P puzzles?

medium

A. O(W * L + P * M), where M is the average number of trie nodes traversed per puzzle

B. O(W * P * L), since each word is checked against each puzzle

C. O(W * 2^7 + P * 7), enumerating all subsets of puzzle letters for each puzzle

D. O(W * L * 26 + P * 26), traversing trie nodes for all letters

Solution

1. Step 1: Analyze word insertion

   Each word is converted to a bitmask and inserted into trie in O(L) time, total O(W * L).

2. Step 2: Analyze puzzle queries

   For each puzzle, dfs traverses trie nodes corresponding to subsets of puzzle letters, average M nodes, total O(P * M).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Matches known optimal complexity [OK]

Hint: Trie traversal depends on subsets of puzzle letters, not all words [OK]

Common Mistakes:

• Assuming brute force complexity
• Confusing 2^7 subsets with trie traversal nodes
• Ignoring average trie traversal cost