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 Python code implementing the optimal backtracking with bitmask and memoization approach for the Matchsticks to Square problem. Given the input [1,1,2,2,2], what is the final return value of makesquare([1,1,2,2,2])?

easy

A. True

B. Depends on the order of matchsticks

C. Raises an exception due to index error

D. False

Solution

1. Step 1: Calculate total and side length

   Total = 1+1+2+2+2 = 8, side = 8/4 = 2.

2. Step 2: Trace backtracking calls

   Sorted sticks: [2,2,2,1,1]. The algorithm tries to form sides of length 2. It can form three sides with three 2's, and the last side with two 1's. Hence, returns true.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sum divisible by 4 and sticks fit sides exactly [OK]

Hint: Sum divisible by 4 and sticks fit sides exactly [OK]

Common Mistakes:

• Forgetting to sort and prune
• Assuming order affects result
• Miscounting sides formed

2. You are given an integer array that may contain duplicates. Your task is to find all possible subsets without duplicate subsets in the result. Which approach guarantees generating all unique subsets efficiently without redundant computations?

easy

A. Generate all subsets using brute force recursion and then filter duplicates by storing subsets in a hash set.

B. Use a greedy algorithm that picks elements only if they are not duplicates of the previous element.

C. Use dynamic programming with a 2D table tracking subset sums to avoid duplicates.

D. Sort the array and use backtracking with skipping duplicates at the same recursion depth to avoid repeated subsets.

Solution

1. Step 1: Understand the problem constraints

   The problem requires generating all unique subsets from an array that may contain duplicates, avoiding duplicate subsets in the output.

2. Step 2: Identify the approach that handles duplicates efficiently

   Sorting the array groups duplicates together, allowing the backtracking algorithm to skip duplicates at the same recursion level, preventing repeated subsets without extra filtering.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Backtracking with sorting and skipping duplicates is the standard pattern for Subsets II [OK]

Hint: Sort and skip duplicates at recursion level [OK]

Common Mistakes:

• Using greedy approach misses some subsets
• DP approach is unrelated to subset generation here
• Brute force with set filtering is inefficient

3. Identify the bug in the following code snippet for counting max bitwise-OR subsets:

from typing import List

class Solution:
    def countMaxOrSubsets(self, nums: List[int]) -> int:
        n = len(nums)
        max_or = 0
        count = 0
        for mask in range(0, 1 << n):  # Note: starts from 0
            current_or = 0
            for i in range(n):
                if mask & (1 << i):
                    current_or |= nums[i]
            if current_or > max_or:
                max_or = current_or
                count = 1
            elif current_or == max_or:
                count += 1
        return count

medium

A. The count variable should be reset inside the inner loop

B. The OR operation should be replaced with AND

C. The loop should start from 1 to exclude empty subset

D. max_or should be initialized to -1 instead of 0

Solution

1. Step 1: Identify that mask=0 represents empty subset

   Empty subset OR is 0, which is usually not counted as a valid subset.

2. Step 2: Recognize that including empty subset inflates count incorrectly

   Starting from mask=0 causes counting empty subset, leading to wrong final count.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Exclude empty subset by starting mask from 1 -> correct counting [OK]

Hint: Empty subset mask=0 must be excluded to avoid incorrect counts [OK]

Common Mistakes:

• Counting empty subset as valid
• Incorrect initialization of max_or

4. Examine the following buggy code snippet for letter case permutation. Which line contains the subtle bug that causes incorrect results on inputs with digits?

def letterCasePermutation(s: str) -> List[str]:
    res = []
    arr = list(s)
    def backtrack(i: int):
        if i == len(arr):
            res.append(''.join(arr))
            return
        if arr[i].isdigit():
            arr[i] = arr[i].upper()  # BUG: digits have no case
            backtrack(i + 1)
        else:
            arr[i] = arr[i].lower()
            backtrack(i + 1)
            arr[i] = arr[i].upper()
            backtrack(i + 1)
            arr[i] = s[i]
    backtrack(0)
    return res

medium

A. Line with 'if i == len(arr):'

B. Line with 'arr[i] = arr[i].upper() # BUG: digits have no case'

C. Line with 'if arr[i].isdigit():'

D. Line with 'arr[i] = s[i]' to revert changes

Solution

1. Step 1: Analyze digit handling

   Digits have no uppercase or lowercase forms, so calling upper() on a digit is unnecessary and incorrect.

2. Step 2: Identify bug impact

   Modifying digits causes incorrect permutations or corrupted results; digits should be left unchanged and recursion called directly.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Digits must be skipped, not toggled [OK]

Hint: Digits must not be modified or toggled [OK]

Common Mistakes:

• Forgetting to revert changes
• Modifying digits as letters

5. Suppose the problem is changed so that candidates can be reused unlimited times (unlike original no reuse). Which modification to the backtracking algorithm correctly adapts to this change?

hard

A. Change recursive call from backtrack(i + 1, ...) to backtrack(i, ...) to allow reuse of the same candidate

B. Keep backtrack(i + 1, ...) but remove duplicate skipping to allow repeated combinations

C. Add a global visited set to prevent reusing candidates in the same combination

D. Sort candidates and prune only when candidate >= target, but keep recursion unchanged

Solution

1. Step 1: Understand reuse requirement

   Allowing reuse means the same candidate index can be chosen multiple times in the same combination.

2. Step 2: Modify recursion call

   Changing recursive call from backtrack(i + 1, ...) to backtrack(i, ...) allows the same candidate to be reused multiple times.

3. Step 3: Keep duplicate skipping and pruning as before

   Duplicate skipping still applies to avoid repeated combinations, and pruning remains to optimize.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Recurse with same index to allow reuse [OK]

Hint: Reuse means recurse with same index, not next index [OK]

Common Mistakes:

• Removing duplicate skipping causes duplicates
• Using visited set breaks reuse logic
• Pruning incorrectly changes conditions