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. Consider the following Python code implementing the optimal backtracking solution for Combination Sum III. What is the final value of res after calling combinationSum3(3, 7)?

easy

A. [[1, 2, 4]]

B. [[1, 3, 3]]

C. [[2, 2, 3]]

D. [[1, 2, 3]]

Solution

1. Step 1: Trace backtracking calls for k=3, n=7

   Start from 1, try combinations of size 3 summing to 7. Valid combos are [1,2,4] only because 1+2+4=7.

2. Step 2: Verify no other combos meet criteria

   Other combos like [1,3,3] or [2,2,3] are invalid due to duplicates or sum mismatch.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Only [1,2,4] sums to 7 with 3 distinct numbers [OK]

Hint: Only distinct numbers summing to 7 with size 3 is [1,2,4] [OK]

Common Mistakes:

• Including duplicates like [1,3,3]
• Miscounting sum or size

2. You are given a set of distinct positive integers and a target sum. You need to find all unique combinations where the chosen numbers sum to the target. Each number can be chosen multiple times. Which algorithmic approach best guarantees finding all valid combinations efficiently without missing any or producing duplicates?

easy

A. Greedy algorithm that picks the largest candidate repeatedly until the sum is reached or exceeded.

B. Backtracking with sorting and frequency counting to avoid duplicates and prune early when sum exceeds target.

C. Dynamic programming using a 2D table to count the number of combinations without generating them explicitly.

D. Pure brute force recursion that tries all subsets without pruning or sorting.

Solution

1. Step 1: Understand problem constraints

   The problem requires all unique combinations summing to target, allowing reuse of candidates.

2. Step 2: Evaluate algorithm suitability

   Greedy fails because it can miss combinations; pure brute force is correct but inefficient; DP counts combinations but doesn't generate them; backtracking with sorting and frequency counting avoids duplicates and prunes search space efficiently.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Backtracking with pruning and frequency counting is the standard approach [OK]

Hint: Backtracking with pruning avoids duplicates and excessive search [OK]

Common Mistakes:

• Assuming greedy always works for sum problems
• Confusing counting with generating combinations

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

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. What is the time complexity of the optimal bitmask + trie solution for the Number of Valid Words for Each Puzzle problem, given W words with average length L, and P puzzles?

medium

A. O(W * L + P * M), where M is the average number of trie nodes traversed per puzzle

B. O(W * P * L), since each word is checked against each puzzle

C. O(W * 2^7 + P * 7), enumerating all subsets of puzzle letters for each puzzle

D. O(W * L * 26 + P * 26), traversing trie nodes for all letters

Solution

1. Step 1: Analyze word insertion

   Each word is converted to a bitmask and inserted into trie in O(L) time, total O(W * L).

2. Step 2: Analyze puzzle queries

   For each puzzle, dfs traverses trie nodes corresponding to subsets of puzzle letters, average M nodes, total O(P * M).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Matches known optimal complexity [OK]

Hint: Trie traversal depends on subsets of puzzle letters, not all words [OK]

Common Mistakes:

• Assuming brute force complexity
• Confusing 2^7 subsets with trie traversal nodes
• Ignoring average trie traversal cost