Subsets

📋

Problem

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

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

Edge cases: Empty input array → output [[]]Single element array → output [[], [element]]All elements are negative → subsets still valid

</>

IDE

def subsets(nums: list[int]) -> list[list[int]]:public List<List<Integer>> subsets(int[] nums)vector<vector<int>> subsets(vector<int>& nums)function subsets(nums)

def subsets(nums: list[int]) -> list[list[int]]:
    # Write your solution here
    pass

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        // Write your solution here
        return new ArrayList<>();
    }
}

#include <vector>
using namespace std;

vector<vector<int>> subsets(vector<int>& nums) {
    // Write your solution here
    return {};
}

function subsets(nums) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: [[1,2,3]]Only including all elements subset, missing empty and partial subsets.✅ Add recursion branch to exclude current element at each step.

Wrong: []Not adding empty subset or missing base case when index == len(nums).✅ Add current subset to result when index == len(nums).

Wrong: [[], [10]]Only one subset returned for single element input, missing either include or exclude branch.✅ Ensure both include and exclude recursive calls are made for each element.

Wrong: Subsets with duplicates when input has duplicatesInput duplicates cause duplicate subsets; code assumes unique input.✅ Enforce input uniqueness or skip duplicates during recursion.

Wrong: Missing subsets due to greedy approachGreedy approach skips exclude branch causing incomplete subsets.✅ Explore both include and exclude branches at each recursion step.

✓

Test Cases

Try testing your code on empty and single-element inputs to catch base case bugs.

Consider tricky inputs that expose greedy or off-by-one errors in recursion.

Prepare for performance testing with maximum input size; optimize your approach.

t1_01basic

Input{"nums":[1,2,3]}

Expected[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

⏱ Performance - must finish in 2000ms

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

💡 Think about including or excluding each element recursively.

💡 Use backtracking with a decision tree of include/exclude at each index.

💡 At each step, add the current subset to the result and recurse on next index.

Why it failed: Output missing subsets or duplicates due to incorrect include/exclude logic. Fix by ensuring both branches (include and exclude) are explored at each recursion.

✓ Correctly generates all subsets using pure include/exclude recursion.

t1_02basic

Input{"nums":[4,5]}

Expected[[],[4],[5],[4,5]]

⏱ Performance - must finish in 2000ms

All subsets of [4,5] generated by including or excluding each element.

💡 Try enumerating subsets by deciding for each element whether to include it.

💡 Backtracking with two recursive calls per element covers all subsets.

💡 Ensure to add the current subset to the result before recursing.

Why it failed: Missing subsets or incorrect subsets due to skipping either include or exclude branch. Fix by calling recursion twice per element: once excluding, once including.

✓ All subsets generated correctly for smaller input.

t2_01edge

Input{"nums":[]}

Expected[[]]

⏱ Performance - must finish in 2000ms

Empty input array returns only the empty subset.

💡 What subsets exist when there are no elements?

💡 The power set of empty set is a set containing the empty set.

💡 Return [[]] when input is empty.

Why it failed: Returned empty list instead of list containing empty subset. Fix by adding base case to append current subset when index == length even if nums is empty.

✓ Correctly returns [[]] for empty input.

t2_02edge

Input{"nums":[10]}

Expected[[],[10]]

⏱ Performance - must finish in 2000ms

Single element array produces empty subset and subset with that element.

💡 For single element, subsets are empty and the element itself.

💡 Include and exclude branches must both be present.

💡 Check recursion handles single element correctly.

Why it failed: Only one subset returned (either empty or single element). Fix by ensuring both include and exclude recursive calls are made.

✓ Both subsets generated correctly for single element input.

t2_03edge

Input{"nums":[-1,-2,-3]}

Expected[[],[-1],[-2],[-1,-2],[-3],[-1,-3],[-2,-3],[-1,-2,-3]]

⏱ Performance - must finish in 2000ms

Negative numbers are valid elements; subsets generated normally.

💡 Negative values do not affect subset generation logic.

💡 Include/exclude decisions are independent of element sign.

💡 Verify code does not filter or alter negative values.

Why it failed: Subsets missing or incorrect due to filtering negative numbers. Fix by treating all elements equally regardless of sign.

✓ Correctly handles negative numbers in subsets.

t3_01corner

Input{"nums":[1,2,2]}

Expected[[],[1],[2],[1,2],[2,2],[1,2,2]]

⏱ Performance - must finish in 2000ms

Input with duplicates (invalid per constraints) to catch if code assumes uniqueness.

💡 Check if code handles duplicates or assumes unique elements.

💡 Duplicates can cause duplicate subsets if not handled.

💡 Add a check or sort and skip duplicates to avoid repeated subsets.

Why it failed: Duplicates in input cause duplicate subsets in output. Fix by enforcing input uniqueness or skipping duplicates during recursion.

✓ Code assumes unique input as per constraints; duplicates cause duplicates subsets.

t3_02corner

Input{"nums":[1,2,3,4]}

Expected[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3],[4],[1,4],[2,4],[1,2,4],[3,4],[1,3,4],[2,3,4],[1,2,3,4]]

⏱ Performance - must finish in 2000ms

Tests if code mistakenly uses greedy approach that picks only some subsets.

💡 Greedy approaches may miss subsets by skipping elements.

💡 Backtracking must explore both include and exclude branches for each element.

💡 Verify recursion covers all 2^n subsets.

Why it failed: Greedy approach misses subsets by not exploring exclude branch. Fix by always recursing on both include and exclude choices.

✓ All subsets generated correctly, no greedy skipping.

t3_03corner

Input{"nums":[1,2,3]}

Expected[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

⏱ Performance - must finish in 2000ms

Test to catch off-by-one errors in recursion index handling.

💡 Check base case triggers exactly when index == length of nums.

💡 Off-by-one errors cause missing or extra subsets.

💡 Ensure recursion stops at index == len(nums) and adds current subset.

Why it failed: Off-by-one error causes missing subsets or infinite recursion. Fix base case to trigger at index == len(nums).

✓ Correct base case and recursion index handling.

t4_01performance

Input{"nums":[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20]}

Expectednull

⏱ Performance - must finish in 2000ms

n=20, O(2^n * n) subsets generation must complete within 2 seconds.

💡 This problem has exponential time complexity O(2^n * n).

💡 Efficient pruning is not possible; expect exponential runtime.

💡 Use iterative or backtracking approach with pruning to optimize memory.

Why it failed: Algorithm exceeds time limit due to exponential complexity O(2^n * n). Fix by optimizing recursion or using iterative bitmask approach.

✓ Algorithm completes within time limit confirming expected complexity.

Practice

1. Consider the following Python code for generating subsets with duplicates. What is the value of res after processing the input [1, 2, 2]?

easy

A. [[], [1], [2], [1, 2], [2, 2], [1, 2, 2]]

B. [[], [1], [2], [1, 2], [2, 2], [1, 2, 2], [2]]

C. [[], [1], [2], [1, 2], [2, 2], [1, 2, 2], [1]]

D. [[], [1], [2], [1, 2], [2, 2], [1, 2, 2], [1, 2]]

Solution

1. Step 1: Trace iterations for input [1, 2, 2]

   Start with res = [[]]. - i=0 (num=1): s=0, start=1, add [1] -> res = [[], [1]] - i=1 (num=2): s=0, start=2, add [2], [1,2] -> res = [[], [1], [2], [1,2]] - i=2 (num=2): duplicate, s=start from previous iteration=2, start=4, add [2,2], [1,2,2] -> res = [[], [1], [2], [1,2], [2,2], [1,2,2]]

2. Step 2: Confirm final res matches option

   The final res contains exactly these subsets without duplicates: [], [1], [2], [1,2], [2,2], [1,2,2].

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Output matches expected unique subsets for input [1,2,2] [OK]

Hint: Duplicate skips start index to avoid repeats [OK]

Common Mistakes:

• Appending duplicates multiple times by resetting s=0 always
• Off-by-one errors in start index
• Including extra subsets from previous iterations

2. What is the time complexity of the optimal backtracking solution for Combination Sum II with n candidates, considering sorting and pruning?

medium

A. O(n^2) due to nested loops and pruning

B. O(2^n * n) because each subset can be generated and copying path costs O(n)

C. O(n * target) similar to classic DP subset sum

D. O(n!) due to permutations of candidates

Solution

1. Step 1: Identify recursion tree size

   Backtracking explores subsets, up to 2^n subsets in worst case.

2. Step 2: Account for path copying cost

   Each valid combination copied costs O(n), so total time is O(2^n * n).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Exponential subsets with path copying dominates [OK]

Hint: Backtracking subsets generate 2^n possibilities, each copied O(n) time [OK]

Common Mistakes:

• Confusing with DP O(n*target)
• Assuming pruning reduces to polynomial
• Thinking permutations cause factorial time

3. The following code attempts to solve Combination Sum (Reuse Allowed). Identify the line containing the subtle bug that causes incorrect results or inefficiency:

def combinationSum(candidates, target):
    candidates.sort()
    result = []
    def backtrack(index, path, target):
        if target == 0:
            result.append(path[:])
            return
        if index == len(candidates) or target < 0:
            return
        max_use = target // candidates[index]
        for count in range(max_use + 1):
            path += [candidates[index]] * count
            backtrack(index + 1, path, target - candidates[index] * count)
            # Missing path restoration here
    backtrack(0, [], target)
    return result

medium

A. Line with 'path += [candidates[index]] * count' because path is modified without backtracking (pop).

B. Line with 'candidates.sort()' because sorting is unnecessary.

C. Line with 'if target == 0:' because it should check for target <= 0.

D. Line with 'max_use = target // candidates[index]' because integer division may cause errors.

Solution

1. Step 1: Analyze path modification in loop

   Path is extended by count copies of candidates[index] but never restored after recursive call, causing path to grow incorrectly across iterations.

2. Step 2: Identify missing backtracking step

   Proper backtracking requires removing added elements after recursion to restore path state for next iteration.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Modifying path without restoration leads to incorrect combinations [OK]

Hint: Always restore path after recursion in backtracking [OK]

Common Mistakes:

• Forgetting to pop elements after recursion
• Assuming path copy avoids mutation issues

4. The following code attempts to find the largest divisible subset but contains a subtle bug. Identify the line with the bug.

def largestDivisibleSubset(nums):
    if not nums:
        return []
    n = len(nums)
    dp = [1] * n
    prev = [-1] * n
    max_index = 0

    for i in range(n):
        for j in range(i - 1, -1, -1):
            if nums[j] % nums[i] == 0:
                if dp[j] + 1 > dp[i]:
                    dp[i] = dp[j] + 1
                    prev[i] = j
            else:
                break
        if dp[i] > dp[max_index]:
            max_index = i

    result = []
    while max_index >= 0:
        result.append(nums[max_index])
        max_index = prev[max_index]
    return result[::-1]

medium

A. Line with 'result.append(nums[max_index])'

B. Line with 'dp = [1] * n'

C. Line with 'max_index = 0'

D. Line with 'if nums[j] % nums[i] == 0:'

Solution

1. Step 1: Check divisibility condition

   The condition should be nums[i] % nums[j] == 0 because we want to check if current number is divisible by a smaller number.

2. Step 2: Understand impact of bug

   Using nums[j] % nums[i] == 0 reverses the divisibility logic, causing incorrect dp updates and wrong subsets.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Correct divisibility check is crucial for correctness [OK]

Hint: Divisibility check direction matters [OK]

Common Mistakes:

• Swapping divisor and dividend in modulo check
• Not sorting input before DP
• Incorrect subset reconstruction

5. What is the time complexity of generating all subsets of an array of size n using bitmask enumeration, and why is the common misconception that it is O(2^n) incorrect?

medium

A. O(n^2) because we iterate over n elements twice

B. O(2^n) because there are 2^n subsets

C. O(n * 2^n) because each subset can have up to n elements and we build each subset by checking n bits

D. O(n) because we process each element once

Solution

1. Step 1: Count subsets and subset size

   There are 2^n subsets, and each subset can have up to n elements.

2. Step 2: Analyze bitmask enumeration cost

   For each of the 2^n masks, we check n bits to build the subset, resulting in O(n * 2^n) time.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Time depends on both number of subsets and subset size [OK]

Hint: Each subset requires O(n) to build, total O(n*2^n) [OK]

Common Mistakes:

• Ignoring subset size in complexity
• Assuming O(2^n) only
• Confusing with DP complexities