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. You are given a list of candidate numbers (which may contain duplicates) and a target sum. You need to find all unique combinations where each candidate number is used at most once and the sum of the combination equals the target. Which algorithmic approach best guarantees finding all unique combinations without duplicates efficiently?

easy

A. Backtracking with sorting candidates, skipping duplicates at the same recursion level, and pruning branches when the candidate exceeds the remaining target

B. Greedy algorithm that picks the largest candidates first until the target is met or exceeded

C. Dynamic programming subset-sum approach without handling duplicates explicitly

D. Brute force recursion without sorting or duplicate checks, exploring all subsets

Solution

1. Step 1: Understand problem constraints

   The problem requires unique combinations without reuse and no duplicate results, so duplicates must be handled carefully.

2. Step 2: Identify suitable algorithm

   Backtracking with sorting and skipping duplicates at the same recursion level ensures no repeated combinations. Early pruning avoids unnecessary recursion when candidates exceed the target.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sorting + duplicate skipping + pruning is the standard approach [OK]

Hint: Sorting and skipping duplicates avoids repeated combinations [OK]

Common Mistakes:

• Using greedy misses some combinations
• DP without duplicate handling outputs duplicates
• Brute force is correct but inefficient and duplicates appear

2. Consider the following Python function that counts subsets with sum K using a space-optimized DP approach. What is the output when called with arr = [1, 2, 3, 3] and K = 6?

def count_subsets_space_optimized(arr, K):
    dp = [0] * (K + 1)
    dp[0] = 1
    for num in arr:
        for j in range(K, num - 1, -1):
            dp[j] += dp[j - num]
    return dp[K]

print(count_subsets_space_optimized(arr, K))

easy

A. 5

B. 4

C. 3

D. 6

Solution

1. Step 1: Initialize dp array

   dp = [1,0,0,0,0,0,0] since dp[0]=1 and K=6.

2. Step 2: Process each number updating dp

   After processing 1: dp = [1,1,0,0,0,0,0] After 2: dp = [1,1,1,1,0,0,0] After first 3: dp = [1,1,1,2,1,1,1] After second 3: dp = [1,1,1,3,2,2,3]

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   dp[6] = 5 subsets sum to 6 [OK]

Hint: Trace dp updates backward to avoid double counting [OK]

Common Mistakes:

• Forgetting to iterate backward in dp array
• Off-by-one errors in dp indices

3. You are given an unsorted array of positive integers. Your task is to find the largest subset such that for every pair (Si, Sj) in the subset, either Si divides Sj or Sj divides Si. Which algorithmic approach guarantees finding the optimal solution efficiently?

easy

A. Greedy approach by always picking the smallest element and adding divisible elements afterwards

B. Use a brute force backtracking to generate all subsets and check divisibility

C. Sort the array and use dynamic programming to build the longest chain where each element divides the next

D. Use a graph traversal to find the largest clique where edges represent divisibility

Solution

1. Step 1: Understand problem constraints

   The problem requires a subset where every pair is divisible in one direction, which suggests a chain-like structure.

2. Step 2: Identify suitable algorithm

   Sorting the array allows divisibility checks to be done efficiently in increasing order, enabling dynamic programming to build the longest divisible chain.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Sorting + DP is classic for largest divisible subset [OK]

Hint: Sort + DP builds longest divisible chain [OK]

Common Mistakes:

• Greedy fails because local choices don't guarantee global maximum
• Brute force is correct but inefficient, not practical
• Graph clique approach is incorrect because divisibility is not symmetric

4. Given the following code to generate subsets, what is the value of result after processing num=2 when nums = [1, 2]?

easy

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

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

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

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

Solution

1. Step 1: Trace result after processing num=1

   Initially result = [[]]. After num=1, new_subsets = [[1]], result = [[], [1]].

2. Step 2: Trace result after processing num=2

   For each subset in [[], [1]], add 2: new_subsets = [[2], [1, 2]]. Extend result: [[], [1], [2], [1, 2]].

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   All subsets of [1,2] are present exactly once [OK]

Hint: Iterative subsets double result size each iteration [OK]

Common Mistakes:

• Forgetting to add subsets with current num
• Appending duplicates
• Wrong order of subsets

5. 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