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. You are given a list of candidate numbers (which may contain duplicates) and a target sum. You need to find all unique combinations where each candidate number is used at most once and the sum of the combination equals the target. Which algorithmic approach best guarantees finding all unique combinations without duplicates efficiently?

easy

A. Backtracking with sorting candidates, skipping duplicates at the same recursion level, and pruning branches when the candidate exceeds the remaining target

B. Greedy algorithm that picks the largest candidates first until the target is met or exceeded

C. Dynamic programming subset-sum approach without handling duplicates explicitly

D. Brute force recursion without sorting or duplicate checks, exploring all subsets

Solution

1. Step 1: Understand problem constraints

   The problem requires unique combinations without reuse and no duplicate results, so duplicates must be handled carefully.

2. Step 2: Identify suitable algorithm

   Backtracking with sorting and skipping duplicates at the same recursion level ensures no repeated combinations. Early pruning avoids unnecessary recursion when candidates exceed the target.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sorting + duplicate skipping + pruning is the standard approach [OK]

Hint: Sorting and skipping duplicates avoids repeated combinations [OK]

Common Mistakes:

• Using greedy misses some combinations
• DP without duplicate handling outputs duplicates
• Brute force is correct but inefficient and duplicates appear

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

3. You are given an unsorted array of positive integers. Your task is to find the largest subset such that for every pair (Si, Sj) in the subset, either Si divides Sj or Sj divides Si. Which algorithmic approach guarantees finding the optimal solution efficiently?

easy

A. Greedy approach by always picking the smallest element and adding divisible elements afterwards

B. Use a brute force backtracking to generate all subsets and check divisibility

C. Sort the array and use dynamic programming to build the longest chain where each element divides the next

D. Use a graph traversal to find the largest clique where edges represent divisibility

Solution

1. Step 1: Understand problem constraints

   The problem requires a subset where every pair is divisible in one direction, which suggests a chain-like structure.

2. Step 2: Identify suitable algorithm

   Sorting the array allows divisibility checks to be done efficiently in increasing order, enabling dynamic programming to build the longest divisible chain.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Sorting + DP is classic for largest divisible subset [OK]

Hint: Sort + DP builds longest divisible chain [OK]

Common Mistakes:

• Greedy fails because local choices don't guarantee global maximum
• Brute force is correct but inefficient, not practical
• Graph clique approach is incorrect because divisibility is not symmetric

4. You are given an array of positive integers and a number k. The task is to determine if the array can be partitioned into k subsets such that the sum of elements in each subset is equal. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Dynamic programming based on subset sums without pruning or memoization

B. Greedy algorithm that picks the largest elements first and assigns them to subsets

C. Backtracking with bitmask memoization to explore subsets and prune invalid states

D. Sorting and then using a sliding window to find equal sum partitions

Solution

1. Step 1: Understand problem constraints and complexity

   The problem requires partitioning into exactly k subsets with equal sums, which is NP-complete and requires exploring combinations exhaustively.

2. Step 2: Evaluate algorithm suitability

   Greedy and sliding window approaches fail to guarantee correctness because they don't explore all combinations. Simple DP without pruning is inefficient and incomplete. Backtracking with bitmask memoization efficiently prunes and caches states, guaranteeing optimality.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Backtracking with memoization handles all subsets optimally [OK]

Hint: Bitmask memoization prunes repeated subset states [OK]

Common Mistakes:

• Assuming greedy always works for equal sum partition
• Confusing subset sum DP with partitioning into k subsets

5. What is the time complexity of the optimal backtracking solution for Combination Sum II with n candidates, considering sorting and pruning?

medium

A. O(n^2) due to nested loops and pruning

B. O(2^n * n) because each subset can be generated and copying path costs O(n)

C. O(n * target) similar to classic DP subset sum

D. O(n!) due to permutations of candidates

Solution

1. Step 1: Identify recursion tree size

   Backtracking explores subsets, up to 2^n subsets in worst case.

2. Step 2: Account for path copying cost

   Each valid combination copied costs O(n), so total time is O(2^n * n).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Exponential subsets with path copying dominates [OK]

Hint: Backtracking subsets generate 2^n possibilities, each copied O(n) time [OK]

Common Mistakes:

• Confusing with DP O(n*target)
• Assuming pruning reduces to polynomial
• Thinking permutations cause factorial time