Combination Sum (Reuse Allowed)

📋

Combination Sum (Reuse Allowed)

Edge cases:

</>

IDE

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

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

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

#include <vector>
using namespace std;

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

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

Common Bugs to Avoid

Wrong: [[7]]Missing combinations that sum to target using multiple smaller candidates.✅ Allow reuse of candidates by not incrementing start index after choosing a candidate.

Wrong: [[2,2,4],[4,4]]Missing combinations due to greedy approach picking largest candidate first.✅ Use backtracking to explore all candidates at each recursion level.

Wrong: [[1,2]]Treating problem as 0/1 knapsack, disallowing reuse of candidates.✅ Allow reuse by calling recursion with same start index after choosing candidate.

Wrong: [[2,2,2,2],[4,4],[2,6],[2,2,4],[2,2,4]]Duplicates due to incorrect recursion indices or path copying.✅ Use start index to avoid duplicates and copy path correctly when adding to results.

Wrong: Timeout or no outputBrute force recursion without pruning causes TLE on large inputs.✅ Implement pruning to skip candidates exceeding target and memoize subproblems.

✓

Test Cases

Focus on handling empty and minimal inputs correctly.

Consider algorithmic pitfalls like greedy traps and reuse confusion.

Think about pruning and memoization to handle large inputs efficiently.

t1_01basic

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

Expected[[2,2,3],[7]]

⏱ Performance - must finish in 2000ms

2+2+3=7 and 7=7 are the only combinations. Reuse of 2 is allowed.

💡 Try backtracking to explore all combinations with reuse allowed.

💡 Use recursion with a start index to avoid duplicates and allow reuse.

💡 Include current candidate multiple times until sum reaches target or exceeds.

Why it failed: Output missing valid combinations or includes invalid ones. Fix by allowing reuse of candidates by not incrementing start index after choosing a candidate.

✓ Correctly finds all unique combinations with reuse allowed.

t1_02basic

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

Expected[[2,2,2,2],[2,2,4],[4,4]]

⏱ Performance - must finish in 2000ms

Valid combinations summing to 8 are [2,2,2,2], [2,2,4], and [4,4]. Note that 1 is not in candidates, so combinations with 1 are invalid and must not appear.

💡 Check all combinations that sum to target using backtracking with reuse.

💡 Avoid including numbers not in candidates; only use given candidates.

💡 Ensure combinations sum exactly to target and no invalid elements included.

Why it failed: Including numbers not in candidates or missing valid combinations. Fix by only choosing from candidates and pruning sums exceeding target.

✓ Correctly enumerates all valid combinations summing to target.

t2_01edge

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

Expected[]

⏱ Performance - must finish in 2000ms

Empty candidates array means no combinations possible.

💡 Check behavior when candidates array is empty.

💡 No candidates means no sums can be formed.

💡 Return empty list immediately if candidates is empty.

Why it failed: Returns non-empty output or errors on empty candidates. Fix by adding base case to return [] if candidates is empty.

✓ Correctly returns empty list for empty candidates.

t2_02edge

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

Expected[[5]]

⏱ Performance - must finish in 2000ms

Single candidate equal to target forms one valid combination.

💡 Check single element candidates equal to target.

💡 Backtracking should find single element combination.

💡 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 equal to target.

t2_03edge

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

Expected[]

⏱ Performance - must finish in 2000ms

Target smaller than smallest candidate means no combinations possible.

💡 Check if target is smaller than all candidates.

💡 No candidate can be used to reach target.

💡 Return empty list if target < min(candidates).

Why it failed: Returns non-empty output for target smaller than smallest candidate. Fix by pruning candidates larger than target before backtracking.

✓ Correctly returns empty list when target < smallest candidate.

t2_04edge

Input{"candidates":[10,20,30],"target":10}

Expected[[10]]

⏱ Performance - must finish in 2000ms

Candidates contain elements larger than target; only 10 equals target and forms valid combination.

💡 Ignore candidates larger than target during backtracking.

💡 Check if candidate equals target to add single-element combination.

💡 Prune candidates exceeding target to optimize search.

Why it failed: Includes candidates larger than target or misses single-element combination. Fix by pruning candidates > target and adding candidate == target.

✓ Correctly handles candidates larger than target.

t3_01corner

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

Expected[[2,2,2,2],[2,3,3],[3,5]]

⏱ Performance - must finish in 2000ms

Multiple combinations exist; greedy approach picking largest first fails to find all.

💡 Greedy picking largest candidate first may miss combinations.

💡 Backtracking explores all combinations, not just greedy picks.

💡 Avoid greedy; try all candidates recursively with reuse.

Why it failed: Greedy approach misses valid combinations like [2,3,3]. Fix by using backtracking to explore all candidates at each step.

✓ Backtracking correctly finds all combinations, avoiding greedy trap.

t3_02corner

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

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

⏱ Performance - must finish in 2000ms

Reuse allowed; confusion with 0/1 knapsack leads to missing repeated elements.

💡 Check if reuse of candidates is allowed or not.

💡 0/1 knapsack disallows reuse; here reuse is allowed.

💡 Allow same candidate multiple times by not incrementing start index after choosing.

Why it failed: Treating problem as 0/1 knapsack misses repeated elements. Fix by allowing reuse of candidates in recursion.

✓ Correctly allows reuse of candidates to form combinations.

t3_03corner

Input{"candidates":[2,4,6],"target":8}

Expected[[2,2,2,2],[2,2,4],[4,4],[2,6]]

⏱ Performance - must finish in 2000ms

Off-by-one errors in recursion can miss combinations or cause duplicates.

💡 Check recursion indices carefully to avoid duplicates.

💡 Use start index to avoid revisiting previous candidates.

💡 Ensure path is copied correctly when adding to results.

Why it failed: Duplicates or missing combinations due to off-by-one errors in recursion indices. Fix by correctly managing start index and path copying.

✓ Recursion indices and path management correctly implemented.

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],"target":500}

Expectednull

⏱ Performance - must finish in 2000ms

n=30 candidates, target=500; brute force exponential time O(N^(T/M)) will TLE; efficient pruning/backtracking needed.

💡 Brute force exponential time will not finish in time.

💡 Use pruning and memoization to reduce search space.

💡 Avoid recomputing subproblems and prune candidates exceeding target.

Why it failed: Brute force or naive recursion causes TLE due to exponential complexity. Fix by implementing pruning and memoization.

✓ Efficient pruning and backtracking complete within time limit.

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. Consider the following code snippet implementing the trie-based solution for counting valid words for puzzles. Given the words = ["apple", "plea", "plead"] and puzzles = ["aelwxyz"], what is the returned count for this puzzle?

easy

A. [1]

B. [0]

C. [2]

D. [3]

Solution

1. Step 1: Compute bitmasks for words

   "apple" -> letters {a,p,l,e}, mask with ≤7 bits; "plea" and "plead" similarly processed.

2. Step 2: Check puzzle "aelwxyz"

   First letter 'a' must be in word; words "apple" and "plea" contain 'a' and are subsets of puzzle letters; "plead" contains 'd' not in puzzle.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Two words match conditions [OK]

Hint: Count words containing puzzle first letter and subset of puzzle letters [OK]

Common Mistakes:

• Counting words missing first letter
• Including words with letters outside puzzle
• Off-by-one in counting matches

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

4. What is the time complexity of the iterative lexicographic combinations generation algorithm for generating all combinations of size k from n elements?

medium

A. O(n^k) because each element can be chosen or not

B. O(k * (n choose k)) since each combination of size k is generated once and updated in O(k)

C. O(\u03C3(n choose k) * k) where \u03C3 is the number of combinations generated

D. O(n * k) because the outer loop runs n times and inner loop k times

Solution

1. Step 1: Identify number of combinations

   There are exactly (n choose k) combinations to generate.

2. Step 2: Analyze per-combination cost

   Each combination is generated and updated in O(k) time due to copying and resetting elements.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Time is proportional to number of combinations times combination size [OK]

Hint: Time depends on number of combinations times k [OK]

Common Mistakes:

• Confusing with exponential O(n^k) or linear O(n*k) complexities

5. What is the time complexity of the bitmask enumeration approach for counting the number of max bitwise-OR subsets in an array of length n?

medium

A. O(n^2)

B. O(n!)

C. O(2^n)

D. O(n * 2^n)

Solution

1. Step 1: Identify outer loop over all subsets

   There are 2^n subsets, so outer loop runs 2^n times.

2. Step 2: Identify inner loop over elements for each subset

   For each subset, we check up to n elements to compute OR, so inner loop is O(n).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   2^n subsets x n elements per subset -> O(n * 2^n) [OK]

Hint: Each subset requires checking n elements -> O(n * 2^n) [OK]

Common Mistakes:

• Confusing 2^n subsets with O(2^n) ignoring inner loop
• Assuming quadratic or factorial complexity