Combination Sum II (No Reuse, Duplicates)

🎯

Combination Sum II (No Reuse, Duplicates)

mediumBACKTRACKINGAmazonGoogle

Imagine you are organizing a gift basket with a fixed budget, and you want to find all unique combinations of items that exactly match your budget without repeating any item.

💡 This problem asks for all unique combinations of numbers that sum to a target, but each number can only be used once. Beginners often struggle with handling duplicates and ensuring no repeated combinations appear in the output.

📋

Problem Statement

Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sum to target. Each number in candidates may only be used once in the combination. The solution set must not contain duplicate combinations.

1 ≤ candidates.length ≤ 1001 ≤ candidates[i] ≤ 501 ≤ target ≤ 500

💡

Example

Input"candidates = [10,1,2,7,6,1,5], target = 8"

Output[[1,1,6],[1,2,5],[1,7],[2,6]]

We find all unique combinations that sum to 8. Note that [1,1,6] appears only once despite two '1's in candidates.

• Empty candidates array → []
• No combination sums to target → []
• All candidates are the same number and sum to target → single combination
• Target smaller than smallest candidate → []

⚠️

Common Mistakes

Not sorting candidates before recursion

Duplicates cannot be detected and skipped, leading to repeated combinations

✅ Sort candidates array before starting backtracking

Skipping duplicates incorrectly (e.g., skipping all duplicates, not just at same recursion level)

Valid combinations may be missed or duplicates still appear

✅ Only skip duplicates when they appear at the same recursion depth (same for-loop level)

Reusing candidates multiple times despite problem stating no reuse

Output includes invalid combinations with repeated elements

✅ Advance index by i+1 in recursion to avoid reuse of same element

Not pruning recursion when candidate > target

Unnecessary recursion calls increase runtime significantly

✅ Break the loop early when candidate exceeds remaining target

Modifying path list in-place without backtracking properly

Results contain incorrect combinations due to shared references

✅ Use path copies or backtrack by removing last element after recursion

🧠

Brute Force (Pure Recursion with Backtracking)

💡 Starting with brute force helps understand the problem structure and recursion tree, even though it is inefficient and duplicates are not handled optimally.

Intuition

Try every possible combination by recursively choosing or skipping each candidate, and check if the sum matches the target. This explores all subsets.

Algorithm

1. Sort the candidates to help identify duplicates later.
2. Recursively explore each candidate starting from current index.
3. Include the candidate and recurse with reduced target and next index.
4. Exclude the candidate and recurse with next index.

💡 The recursion explores all subsets but does not yet handle duplicates properly, so it may generate repeated combinations.

</>

Code

from typing import List

def combinationSum2(candidates: List[int], target: int) -> List[List[int]]:
    candidates.sort()
    res = []
    def backtrack(start, path, target):
        if target == 0:
            res.append(path[:])
            return
        if target < 0:
            return
        for i in range(start, len(candidates)):
            # No duplicate handling here
            backtrack(i + 1, path + [candidates[i]], target - candidates[i])
    backtrack(0, [], target)
    return res

# Driver code
if __name__ == '__main__':
    print(combinationSum2([10,1,2,7,6,1,5], 8))

Line Notes

candidates.sort()Sorting helps to identify duplicates in later approaches

def backtrack(start, path, target):Defines recursive function exploring subsets from 'start'

if target == 0:Base case: found a valid combination summing to target

for i in range(start, len(candidates))Try each candidate starting from current index

import java.util.*;

public class CombinationSum2 {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> res = new ArrayList<>();
        backtrack(candidates, target, 0, new ArrayList<>(), res);
        return res;
    }

    private void backtrack(int[] candidates, int target, int start, List<Integer> path, List<List<Integer>> res) {
        if (target == 0) {
            res.add(new ArrayList<>(path));
            return;
        }
        if (target < 0) return;
        for (int i = start; i < candidates.length; i++) {
            // No duplicate handling here
            path.add(candidates[i]);
            backtrack(candidates, target - candidates[i], i + 1, path, res);
            path.remove(path.size() - 1);
        }
    }

    public static void main(String[] args) {
        CombinationSum2 sol = new CombinationSum2();
        System.out.println(sol.combinationSum2(new int[]{10,1,2,7,6,1,5}, 8));
    }
}

Line Notes

Arrays.sort(candidates);Sorting to prepare for duplicate detection in better approaches

private void backtrack(...)Recursive helper exploring subsets from 'start' index

if (target == 0)Found a valid combination, add a copy to results

for (int i = start; i < candidates.length; i++)Try each candidate from current index

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        vector<vector<int>> res;
        vector<int> path;
        backtrack(candidates, target, 0, path, res);
        return res;
    }

    void backtrack(vector<int>& candidates, int target, int start, vector<int>& path, vector<vector<int>>& res) {
        if (target == 0) {
            res.push_back(path);
            return;
        }
        if (target < 0) return;
        for (int i = start; i < candidates.size(); i++) {
            // No duplicate handling here
            path.push_back(candidates[i]);
            backtrack(candidates, target - candidates[i], i + 1, path, res);
            path.pop_back();
        }
    }
};

int main() {
    Solution sol;
    vector<int> candidates = {10,1,2,7,6,1,5};
    vector<vector<int>> res = sol.combinationSum2(candidates, 8);
    for (auto &comb : res) {
        cout << "[";
        for (int i = 0; i < comb.size(); i++) {
            cout << comb[i];
            if (i != comb.size() - 1) cout << ",";
        }
        cout << "]\n";
    }
    return 0;
}

Line Notes

sort(candidates.begin(), candidates.end());Sort to prepare for duplicate handling later

void backtrack(...)Recursive function exploring subsets from 'start'

if (target == 0)Base case: found valid combination

for (int i = start; i < candidates.size(); i++)Try each candidate starting from current index

function combinationSum2(candidates, target) {
    candidates.sort((a,b) => a - b);
    const res = [];
    function backtrack(start, path, target) {
        if (target === 0) {
            res.push([...path]);
            return;
        }
        if (target < 0) return;
        for (let i = start; i < candidates.length; i++) {
            // No duplicate handling here
            path.push(candidates[i]);
            backtrack(i + 1, path, target - candidates[i]);
            path.pop();
        }
    }
    backtrack(0, [], target);
    return res;
}

// Test
console.log(combinationSum2([10,1,2,7,6,1,5], 8));

Line Notes

candidates.sort((a,b) => a - b);Sort to help identify duplicates in better approaches

function backtrack(start, path, target)Recursive helper exploring subsets from 'start'

if (target === 0)Found a valid combination, add a copy to results

for (let i = start; i < candidates.length; i++)Try each candidate starting from current index

⏱

Complexity

TimeO(2^n * n)

SpaceO(n)

We explore all subsets (2^n) and copying paths costs O(n) each time we find a valid combination.

💡 For n=15, 2^15=32768 subsets, which is already large and inefficient.

Interview Verdict: TLE / Inefficient for large inputs

This approach is too slow and produces duplicates, but it helps understand the problem structure.

🧠

Backtracking with Sorting and Duplicate Skipping

💡 This approach improves brute force by sorting and skipping duplicates at the same recursion level to avoid repeated combinations.

Intuition

Sort candidates so duplicates are adjacent. When iterating, skip candidates equal to the previous one at the same recursion depth to avoid duplicate combinations.

Algorithm

1. Sort candidates to group duplicates.
2. Recursively explore candidates starting from current index.
3. Skip candidates that are the same as previous at the same recursion level.
4. Include candidate and recurse with next index and reduced target.

💡 Skipping duplicates at the same recursion level is key to avoid repeated combinations.

</>

Code

from typing import List

def combinationSum2(candidates: List[int], target: int) -> List[List[int]]:
    candidates.sort()
    res = []
    def backtrack(start, path, target):
        if target == 0:
            res.append(path[:])
            return
        if target < 0:
            return
        prev = -1
        for i in range(start, len(candidates)):
            if candidates[i] == prev:
                continue
            prev = candidates[i]
            backtrack(i + 1, path + [candidates[i]], target - candidates[i])
    backtrack(0, [], target)
    return res

# Driver code
if __name__ == '__main__':
    print(combinationSum2([10,1,2,7,6,1,5], 8))

Line Notes

candidates.sort()Sort to group duplicates for skipping

prev = -1Initialize previous candidate to track duplicates at this level

if candidates[i] == prev:Skip duplicate candidates at same recursion depth

backtrack(i + 1, path + [candidates[i]], target - candidates[i])Recurse with next index and updated target

import java.util.*;

public class CombinationSum2 {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> res = new ArrayList<>();
        backtrack(candidates, target, 0, new ArrayList<>(), res);
        return res;
    }

    private void backtrack(int[] candidates, int target, int start, List<Integer> path, List<List<Integer>> res) {
        if (target == 0) {
            res.add(new ArrayList<>(path));
            return;
        }
        if (target < 0) return;
        int prev = -1;
        for (int i = start; i < candidates.length; i++) {
            if (candidates[i] == prev) continue;
            prev = candidates[i];
            path.add(candidates[i]);
            backtrack(candidates, target - candidates[i], i + 1, path, res);
            path.remove(path.size() - 1);
        }
    }

    public static void main(String[] args) {
        CombinationSum2 sol = new CombinationSum2();
        System.out.println(sol.combinationSum2(new int[]{10,1,2,7,6,1,5}, 8));
    }
}

Line Notes

Arrays.sort(candidates);Sort to group duplicates for skipping

int prev = -1;Track previous candidate to skip duplicates at this level

if (candidates[i] == prev) continue;Skip duplicate candidates at same recursion depth

backtrack(candidates, target - candidates[i], i + 1, path, res);Recurse with next index and updated target

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        vector<vector<int>> res;
        vector<int> path;
        backtrack(candidates, target, 0, path, res);
        return res;
    }

    void backtrack(vector<int>& candidates, int target, int start, vector<int>& path, vector<vector<int>>& res) {
        if (target == 0) {
            res.push_back(path);
            return;
        }
        if (target < 0) return;
        int prev = -1;
        for (int i = start; i < candidates.size(); i++) {
            if (candidates[i] == prev) continue;
            prev = candidates[i];
            path.push_back(candidates[i]);
            backtrack(candidates, target - candidates[i], i + 1, path, res);
            path.pop_back();
        }
    }
};

int main() {
    Solution sol;
    vector<int> candidates = {10,1,2,7,6,1,5};
    vector<vector<int>> res = sol.combinationSum2(candidates, 8);
    for (auto &comb : res) {
        cout << "[";
        for (int i = 0; i < comb.size(); i++) {
            cout << comb[i];
            if (i != comb.size() - 1) cout << ",";
        }
        cout << "]\n";
    }
    return 0;
}

Line Notes

sort(candidates.begin(), candidates.end());Sort to group duplicates for skipping

int prev = -1;Track previous candidate to skip duplicates at this level

if (candidates[i] == prev) continue;Skip duplicate candidates at same recursion depth

backtrack(candidates, target - candidates[i], i + 1, path, res);Recurse with next index and updated target

function combinationSum2(candidates, target) {
    candidates.sort((a,b) => a - b);
    const res = [];
    function backtrack(start, path, target) {
        if (target === 0) {
            res.push([...path]);
            return;
        }
        if (target < 0) return;
        let prev = -1;
        for (let i = start; i < candidates.length; i++) {
            if (candidates[i] === prev) continue;
            prev = candidates[i];
            path.push(candidates[i]);
            backtrack(i + 1, path, target - candidates[i]);
            path.pop();
        }
    }
    backtrack(0, [], target);
    return res;
}

// Test
console.log(combinationSum2([10,1,2,7,6,1,5], 8));

Line Notes

candidates.sort((a,b) => a - b);Sort to group duplicates for skipping

let prev = -1;Track previous candidate to skip duplicates at this level

if (candidates[i] === prev) continue;Skip duplicate candidates at same recursion depth

backtrack(i + 1, path, target - candidates[i]);Recurse with next index and updated target

⏱

Complexity

TimeO(2^n * n)

SpaceO(n)

Still explores subsets but pruning duplicates reduces redundant paths; copying paths costs O(n).

💡 For n=15, this is much faster than brute force but still exponential in worst case.

Interview Verdict: Accepted / Efficient for typical inputs

This is the standard approach to solve the problem efficiently in interviews.

🧠

Backtracking with Sorting, Duplicate Skipping, and Early Pruning

💡 This approach adds early pruning by stopping recursion when candidates exceed the remaining target, improving efficiency.

Intuition

Since candidates are sorted, if the current candidate is greater than the remaining target, no need to explore further as all next candidates will be larger.

Algorithm

1. Sort candidates to group duplicates and enable pruning.
2. Recursively explore candidates starting from current index.
3. Skip duplicates at the same recursion level.
4. If candidate > target, break early to prune search space.
5. Include candidate and recurse with next index and reduced target.

💡 Early pruning reduces unnecessary recursion calls, speeding up the search.

</>

Code

from typing import List

def combinationSum2(candidates: List[int], target: int) -> List[List[int]]:
    candidates.sort()
    res = []
    def backtrack(start, path, target):
        if target == 0:
            res.append(path[:])
            return
        prev = -1
        for i in range(start, len(candidates)):
            if candidates[i] > target:
                break
            if candidates[i] == prev:
                continue
            prev = candidates[i]
            backtrack(i + 1, path + [candidates[i]], target - candidates[i])
    backtrack(0, [], target)
    return res

# Driver code
if __name__ == '__main__':
    print(combinationSum2([10,1,2,7,6,1,5], 8))

Line Notes

candidates.sort()Sort to enable duplicate skipping and pruning

if candidates[i] > target:Prune recursion early if candidate exceeds remaining target

if candidates[i] == prev:Skip duplicates at same recursion level

backtrack(i + 1, path + [candidates[i]], target - candidates[i])Recurse with next index and updated target

import java.util.*;

public class CombinationSum2 {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> res = new ArrayList<>();
        backtrack(candidates, target, 0, new ArrayList<>(), res);
        return res;
    }

    private void backtrack(int[] candidates, int target, int start, List<Integer> path, List<List<Integer>> res) {
        if (target == 0) {
            res.add(new ArrayList<>(path));
            return;
        }
        int prev = -1;
        for (int i = start; i < candidates.length; i++) {
            if (candidates[i] > target) break;
            if (candidates[i] == prev) continue;
            prev = candidates[i];
            path.add(candidates[i]);
            backtrack(candidates, target - candidates[i], i + 1, path, res);
            path.remove(path.size() - 1);
        }
    }

    public static void main(String[] args) {
        CombinationSum2 sol = new CombinationSum2();
        System.out.println(sol.combinationSum2(new int[]{10,1,2,7,6,1,5}, 8));
    }
}

Line Notes

Arrays.sort(candidates);Sort to enable duplicate skipping and pruning

if (candidates[i] > target) break;Prune recursion early if candidate exceeds remaining target

if (candidates[i] == prev) continue;Skip duplicates at same recursion level

backtrack(candidates, target - candidates[i], i + 1, path, res);Recurse with next index and updated target

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        vector<vector<int>> res;
        vector<int> path;
        backtrack(candidates, target, 0, path, res);
        return res;
    }

    void backtrack(vector<int>& candidates, int target, int start, vector<int>& path, vector<vector<int>>& res) {
        if (target == 0) {
            res.push_back(path);
            return;
        }
        int prev = -1;
        for (int i = start; i < candidates.size(); i++) {
            if (candidates[i] > target) break;
            if (candidates[i] == prev) continue;
            prev = candidates[i];
            path.push_back(candidates[i]);
            backtrack(candidates, target - candidates[i], i + 1, path, res);
            path.pop_back();
        }
    }
};

int main() {
    Solution sol;
    vector<int> candidates = {10,1,2,7,6,1,5};
    vector<vector<int>> res = sol.combinationSum2(candidates, 8);
    for (auto &comb : res) {
        cout << "[";
        for (int i = 0; i < comb.size(); i++) {
            cout << comb[i];
            if (i != comb.size() - 1) cout << ",";
        }
        cout << "]\n";
    }
    return 0;
}

Line Notes

sort(candidates.begin(), candidates.end());Sort to enable duplicate skipping and pruning

if (candidates[i] > target) break;Prune recursion early if candidate exceeds remaining target

if (candidates[i] == prev) continue;Skip duplicates at same recursion level

backtrack(candidates, target - candidates[i], i + 1, path, res);Recurse with next index and updated target

function combinationSum2(candidates, target) {
    candidates.sort((a,b) => a - b);
    const res = [];
    function backtrack(start, path, target) {
        if (target === 0) {
            res.push([...path]);
            return;
        }
        let prev = -1;
        for (let i = start; i < candidates.length; i++) {
            if (candidates[i] > target) break;
            if (candidates[i] === prev) continue;
            prev = candidates[i];
            path.push(candidates[i]);
            backtrack(i + 1, path, target - candidates[i]);
            path.pop();
        }
    }
    backtrack(0, [], target);
    return res;
}

// Test
console.log(combinationSum2([10,1,2,7,6,1,5], 8));

Line Notes

candidates.sort((a,b) => a - b);Sort to enable duplicate skipping and pruning

if (candidates[i] > target) break;Prune recursion early if candidate exceeds remaining target

if (candidates[i] === prev) continue;Skip duplicates at same recursion level

backtrack(i + 1, path, target - candidates[i]);Recurse with next index and updated target

⏱

Complexity

TimeO(2^n * n)

SpaceO(n)

Early pruning reduces recursion calls, but worst case remains exponential; path copying costs O(n).

💡 For n=20, pruning can significantly reduce runtime compared to brute force.

Interview Verdict: Accepted / Optimal backtracking solution

This is the recommended approach to implement in interviews for this problem.

📊

All Approaches - One-Glance Tradeoffs

💡 Approach 3 is the best to code in interviews; Approach 1 is only for explanation; Approach 2 is a stepping stone.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(2^n * n)	O(n)	Yes (deep recursion)	Yes	Mention only - never code
2. Backtracking with Duplicate Skipping	O(2^n * n)	O(n)	Yes	Yes	Good to explain and code if time permits
3. Backtracking with Duplicate Skipping and Early Pruning	O(2^n * n) but faster in practice	O(n)	Yes	Yes	Best approach to implement in interviews

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Step 1: Clarify problem constraints and ask about duplicates and reuse.Step 2: Present brute force recursion to explore all subsets.Step 3: Improve by sorting and skipping duplicates at recursion level.Step 4: Add early pruning to optimize runtime.Step 5: Code the final approach and test with examples.

Time Allocation

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

What the Interviewer Tests

Ability to handle duplicates correctly, implement backtracking with pruning, and communicate complexity tradeoffs.

Common Follow-ups

• What if candidates can be reused unlimited times? → Use Combination Sum I approach.
• How to handle very large input arrays? → Use pruning and possibly iterative methods.
• Can you return count of combinations instead of all? → Use DP or memoization.
• What if output order matters? → Sort results or use ordered data structures.

💡 These follow-ups test your flexibility and understanding of variations on the problem.

🔍

Pattern Recognition

When to Use

1) Need all unique combinations; 2) Each element used once; 3) Sum constraint; 4) Input may have duplicates.

Signature Phrases

unique combinationseach number only onceno duplicate combinationssum to target

NOT This Pattern When

Problems allowing unlimited reuse or permutations without sum constraints

Similar Problems

Combination Sum I - allows reuse of elementsSubsets II - find unique subsets without sum constraintPermutations II - unique permutations with duplicates

Practice

1. You need to generate all possible subsets of a given set of distinct integers. Which approach guarantees generating every subset exactly once with a time complexity proportional to the number of subsets times the size of each subset?

easy

A. Greedy algorithm that picks elements based on their value order

B. Enumerate all bitmasks from 0 to 2^n - 1, selecting elements where bits are set

C. Dynamic programming to count subsets without generating them

D. Sorting the array and using two pointers to find pairs

Solution

1. Step 1: Understand the problem

   We want to generate all subsets of a set, which are 2^n in number.

2. Step 2: Identify the approach that enumerates all subsets

   Bitmask enumeration from 0 to 2^n - 1 maps each bit to an element's inclusion, guaranteeing all subsets exactly once.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Bitmask enumeration covers all subsets systematically [OK]

Hint: Bitmask from 0 to 2^n-1 enumerates all subsets [OK]

Common Mistakes:

• Thinking greedy or sorting can generate all subsets efficiently

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

3. Suppose the problem changes: now candidates can include negative numbers, and you still want all unique combinations summing to the target with reuse allowed. Which modification to the backtracking approach is necessary to handle this variant correctly?

hard

A. Remove pruning on target < 0 and add a visited set to detect cycles to avoid infinite recursion.

B. No change needed; the existing backtracking with pruning on target < 0 still works correctly.

C. Sort candidates in descending order and prune when target is less than the smallest candidate.

D. Use dynamic programming instead of backtracking because negative numbers break recursion.

Solution

1. Step 1: Understand impact of negative candidates

   Negative numbers allow sums to decrease indefinitely, causing infinite recursion if pruning on target < 0 is used or missing.

2. Step 2: Modify pruning and cycle detection

   Pruning on target < 0 is invalid because target can oscillate; must remove it and add a visited set or memoization to detect repeated states and avoid infinite loops.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Cycle detection is essential when negative numbers allow infinite recursion [OK]

Hint: Negative numbers require cycle detection to prevent infinite recursion [OK]

Common Mistakes:

• Assuming pruning on target < 0 always applies
• Ignoring infinite recursion caused by negatives

4. Suppose you want to generate all combinations of size k from numbers 1 to n, but now elements can be reused multiple times in a combination (combinations with replacement). Which modification to the backtracking approach correctly handles this?

hard

A. Use iterative lexicographic generation without any changes

B. Change the recursive call to backtrack(i + 1, path) to prevent reuse of elements

C. Change the recursive call to backtrack(i, path) to allow reuse of the current element

D. Sort the input array before backtracking to handle duplicates

Solution

1. Step 1: Understand combinations with replacement allow repeated elements

   To allow reuse, the recursive call must not increment start index beyond current element.

2. Step 2: Modify recursion to backtrack(i, path) to allow current element reuse

   This ensures the same element can be chosen multiple times in subsequent recursive calls.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Using backtrack(i, path) enables combinations with replacement [OK]

Hint: Reuse requires recursive calls with same start index [OK]

Common Mistakes:

• Incrementing start index prevents element reuse

5. Suppose the problem is modified so that each element in the array can be used multiple times to form the k equal sum subsets (i.e., unlimited reuse of elements). Which modification to the backtracking with bitmask memoization approach is necessary to correctly solve this variant?

hard

A. Keep bitmask but allow resetting bits after each recursive call

B. Sort ascending instead of descending to handle reuse properly

C. Use the same code without changes because bitmask handles reuse implicitly

D. Remove bitmask usage since elements can be reused; track counts instead

Solution

1. Step 1: Understand reuse impact on state representation

   Bitmask tracks used elements uniquely; with reuse allowed, usage state is not binary but counts.

2. Step 2: Modify approach accordingly

   Bitmask must be removed or replaced by frequency counts to track how many times each element is used; otherwise, states are incorrect.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Bitmask cannot represent multiple uses of same element [OK]

Hint: Bitmask tracks usage once; reuse breaks this assumption [OK]

Common Mistakes:

• Trying to reuse bitmask for multiple uses
• Ignoring state representation changes