Combination Sum II (No Reuse, Duplicates)

📋

Combination Sum II (No Reuse, Duplicates)

Edge cases:

</>

IDE

def combinationSum2(candidates: List[int], target: int) -> List[List[int]]:public List<List<Integer>> combinationSum2(int[] candidates, int target)vector<vector<int>> combinationSum2(vector<int>& candidates, int target)function combinationSum2(candidates, target)

def combinationSum2(candidates, target):
    # Write your solution here
    pass

class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        // Write your solution here
        return new ArrayList<>();
    }
}

#include <vector>
using namespace std;

vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
    // Write your solution here
    return {};
}

function combinationSum2(candidates, target) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: [[1,1,6],[1,2,5],[1,7],[2,6],[1,1,6]]Duplicates not skipped at the same recursion depth, causing repeated combinations.✅ Add condition to skip candidates[i] if candidates[i] == candidates[i-1] and i > start.

Wrong: [[1,2,2],[5],[2,2,1]]Order of elements not normalized or duplicates not skipped, causing repeated combinations with different order.✅ Sort candidates and skip duplicates at the same recursion level; ensure output combinations are sorted.

Wrong: [[1,1],[1,1],[1,1],[1,1]]Duplicate combinations generated due to missing duplicate skipping in input with all identical elements.✅ Skip duplicates at the same recursion depth by checking candidates[i] == candidates[i-1].

Wrong: [[2,2,3],[7]]Treating problem as unbounded knapsack, allowing reuse of candidates.✅ Increment start index in recursion to prevent reuse: backtrack(i+1, ...).

Wrong: Timeout or no outputBrute force exponential complexity without pruning or duplicate skipping.✅ Implement pruning by stopping recursion when candidate > remaining target and skip duplicates.

✓

Test Cases

Focus on handling empty and minimal inputs correctly before moving on.

Ensure your recursion correctly handles no reuse and duplicates before tackling tricky cases.

Optimize your solution with pruning and duplicate skipping to handle large inputs.

t1_01basic

Input{"candidates":[10,1,2,7,6,1,5],"target":8}

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

⏱ Performance - must finish in 2000ms

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

💡 Try sorting candidates and use backtracking to explore combinations.

💡 Skip duplicates at the same recursion depth to avoid repeated combinations.

💡 Use a condition to skip candidates[i] if it's the same as candidates[i-1] at the same level.

Why it failed: Failed to handle duplicates properly; likely missing duplicate skipping logic at the same recursion level. Fix by adding a check to skip candidates[i] if candidates[i] == candidates[i-1] and i > start.

✓ Correctly handles duplicates and finds all unique combinations.

t1_02basic

Input{"candidates":[2,5,2,1,2],"target":5}

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

⏱ Performance - must finish in 2000ms

Unique combinations summing to 5 are [1,2,2] and [5]. Duplicate 2's handled correctly.

💡 Sort candidates to group duplicates together.

💡 Use backtracking with duplicate skipping to avoid repeated combinations.

💡 Skip candidates[i] if it's the same as candidates[i-1] at the same recursion depth.

Why it failed: Incorrect output due to missing duplicate skipping; duplicates cause repeated combinations. Fix by skipping candidates[i] when equal to candidates[i-1] at the same recursion level.

✓ Correctly returns unique combinations without duplicates.

t2_01edge

Input{"candidates":[],"target":7}

Expected[]

⏱ Performance - must finish in 2000ms

Empty candidates array means no combinations possible.

💡 Check if candidates array is empty before processing.

💡 Backtracking should return empty list if no candidates.

💡 Return empty list immediately if candidates is empty.

Why it failed: Code crashes or returns non-empty result on empty candidates. Fix by adding a base case to return [] if candidates is empty.

✓ Correctly handles empty candidates input.

t2_02edge

Input{"candidates":[3],"target":3}

Expected[[3]]

⏱ Performance - must finish in 2000ms

Single element equal to target forms one valid combination.

💡 Test base case with single candidate equal to target.

💡 Backtracking should include candidate if it equals target.

💡 Return [[candidate]] if candidate equals target.

Why it failed: Fails to include single candidate equal to target. Fix by checking if candidate equals target and adding it to results.

✓ Correctly returns single-element combination matching target.

t2_03edge

Input{"candidates":[1,1,1,1],"target":2}

Expected[[1,1]]

⏱ Performance - must finish in 2000ms

All candidates identical; only one unique combination of two 1's sums to 2.

💡 Handle duplicates carefully to avoid repeated combinations.

💡 Skip duplicates at the same recursion depth.

💡 Use condition to skip candidates[i] if candidates[i] == candidates[i-1] at same level.

Why it failed: Returns multiple duplicate combinations due to missing duplicate skipping. Fix by skipping duplicates at the same recursion level.

✓ Correctly returns single unique combination despite duplicates.

t2_04edge

Input{"candidates":[5,10,12],"target":3}

Expected[]

⏱ Performance - must finish in 2000ms

Target smaller than smallest candidate means no valid combinations.

💡 Check if target is smaller than smallest candidate.

💡 Backtracking should return empty list if no candidates fit target.

💡 Return [] immediately if target < min(candidates).

Why it failed: Incorrectly returns non-empty result when target < smallest candidate. Fix by pruning recursion when candidate > target.

✓ Correctly returns empty list when no candidates fit target.

t3_01corner

Input{"candidates":[1,2,3,4,5],"target":10}

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

⏱ Performance - must finish in 2000ms

Multiple unique combinations sum to 10 without reuse: [1,2,3,4], [1,4,5], and [2,3,5].

💡 Check that each candidate is used at most once.

💡 Avoid reusing candidates by incrementing start index in recursion.

💡 Use start = i + 1 in recursive calls to prevent reuse.

Why it failed: Incorrect output includes repeated use of candidates or misses valid combinations. Fix by ensuring recursive calls use start = i + 1 to avoid reuse and explore all combinations.

✓ Correctly enforces no reuse of candidates and finds all unique combinations.

t3_02corner

Input{"candidates":[2,3,6,7],"target":7}

Expected[[7]]

⏱ Performance - must finish in 2000ms

Only single candidate 7 sums to target; no reuse allowed.

💡 Do not treat problem as unbounded knapsack (no reuse).

💡 Ensure each candidate is used once by incrementing start index.

💡 Avoid adding same candidate multiple times by using start = i + 1.

Why it failed: Incorrectly includes [2,2,3] or other repeated candidates. Fix by incrementing start index to prevent reuse.

✓ Correctly distinguishes 0/1 usage from unbounded.

t3_03corner

Input{"candidates":[1,1,2,5],"target":4}

Expected[[1,1,2]]

⏱ Performance - must finish in 2000ms

Duplicate 1's handled correctly; only one unique combination sums to 4.

💡 Beware of greedy approaches that pick first candidates only.

💡 Backtracking explores all subsets with duplicate skipping.

💡 Use sorting and skip duplicates at same recursion level to avoid missing combos.

Why it failed: Greedy approach misses [1,1,2] and returns incomplete results. Fix by full backtracking with duplicate skipping.

✓ Backtracking correctly finds all unique combinations.

t4_01performance

Input{"candidates":[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50],"target":250}

Expectednull

⏱ Performance - must finish in 2000ms

Large input with n=100 candidates and target=250; O(2^n * n) brute force will time out.

💡 Brute force exponential time will not finish in time.

💡 Use backtracking with pruning and duplicate skipping to optimize.

💡 Sort candidates and prune recursion when candidate > remaining target.

Why it failed: TLE due to exponential brute force complexity O(2^n * n). Fix by pruning and skipping duplicates.

✓ Algorithm runs within time limit using pruning and duplicate skipping.

Practice

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

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

3. Examine the following buggy code snippet from the trie-based solution. Which line contains the subtle bug that causes incorrect counts for some puzzles?

medium

A. Line where node.count is incremented

B. Line missing filtering words with more than 7 unique letters before insertion

C. Line checking if bit is set in mask during insertion

D. Line checking if puzzle_mask contains child bit during dfs

Solution

1. Step 1: Identify filtering step

   The code inserts all words regardless of unique letter count, causing large trie and slow traversal.

2. Step 2: Understand impact

   Words with >7 unique letters cannot match puzzles (7 letters max), so filtering them out is necessary for correctness and efficiency.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Filtering missing leads to incorrect counts and performance issues [OK]

Hint: Filter words with >7 unique letters before insertion [OK]

Common Mistakes:

• Not filtering large words
• Incorrect bit checks
• Misplaced count increments

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

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