Combination Sum (Reuse Allowed)

▶

Steps

setup

Start: Sort candidates and begin backtracking

Candidates are sorted to ensure combinations are built in order. The backtracking starts at index 0 with an empty path and target 7.

💡 Sorting helps avoid duplicates and ensures combinations are generated in a consistent order.

Line:

candidates.sort()
backtrack(0, [], target)

💡 The algorithm prepares to explore candidates from smallest to largest, starting fresh with no elements chosen.

choose

Try using candidate 2 zero times

At index 0 (candidate 2), try count = 0, so path remains empty and target stays 7. Recurse to next candidate index 1.

💡 Trying zero times means skipping this candidate and moving on, exploring combinations without 2.

Line:

for count in range(max_use + 1):
    backtrack(index + 1, path + [candidates[index]] * count, target - candidates[index] * count)

💡 The algorithm explores the branch where candidate 2 is not used at all.

choose

Try using candidate 3 zero times

At index 1 (candidate 3), try count = 0, path still empty, target 7. Recurse to index 2.

💡 Again, skipping candidate 3 to explore combinations without 2 or 3.

Line:

for count in range(max_use + 1):
    backtrack(index + 1, path + [candidates[index]] * count, target - candidates[index] * count)

💡 The algorithm explores the branch excluding candidate 3 as well.

choose

Try using candidate 6 zero times

At index 2 (candidate 6), try count = 0, path empty, target 7. Recurse to index 3.

💡 Skipping candidate 6 to explore combinations without 2, 3, or 6.

Line:

for count in range(max_use + 1):
    backtrack(index + 1, path + [candidates[index]] * count, target - candidates[index] * count)

💡 The algorithm continues exploring deeper candidates without using current one.

choose

Try using candidate 7 zero times

At index 3 (candidate 7), try count = 0, path empty, target 7. Recurse to index 4 (end).

💡 Skipping candidate 7 means no candidates chosen, target still 7, no solution here.

Line:

for count in range(max_use + 1):
    backtrack(index + 1, path + [candidates[index]] * count, target - candidates[index] * count)

💡 Reached end of candidates without hitting target 0, this path ends.

choose

Try using candidate 7 one time

Back at index 3, try count = 1, path becomes [7], target reduces to 0. Valid combination found.

💡 Using candidate 7 once exactly matches the target, so this path is a solution.

Line:

backtrack(index + 1, path + [candidates[index]] * count, target - candidates[index] * count)

💡 The algorithm finds a valid combination and adds it to results.

backtracking

Backtrack to index 3, finish trying candidate 7

All counts for candidate 7 tried (0 and 1). Backtrack to index 2 to try next counts for candidate 6.

💡 After exploring all options for a candidate, recursion returns to previous level to try other counts.

Line:

for count in range(max_use + 1):
    backtrack(...)

💡 Backtracking allows exploring all combinations systematically.

choose

Try using candidate 6 one time

At index 2, try count = 1, path becomes [6], target reduces to 1. Recurse to index 3.

💡 Using candidate 6 once reduces target but does not reach zero, so recursion continues.

Line:

backtrack(index + 1, path + [candidates[index]] * count, target - candidates[index] * count)

💡 Partial combinations are built and explored further.

choose

Try using candidate 7 zero times with path [6]

At index 3, try count = 0, path remains [6], target 1. Recurse to index 4 (end).

💡 Skipping candidate 7 here means no solution since target is not zero.

Line:

for count in range(max_use + 1):
    backtrack(...)

💡 No valid combination found on this path, recursion will backtrack.

choose

Backtrack to index 2, try using candidate 3 one time

Back at index 1, try count = 1 for candidate 3, path becomes [3], target reduces to 4. Recurse to index 2.

💡 Trying candidate 3 once to explore new partial sums.

Line:

backtrack(index + 1, path + [candidates[index]] * count, target - candidates[index] * count)

💡 The algorithm explores new branches by including candidates multiple times.

choose

Try using candidate 6 zero times with path [3]

At index 2, try count = 0, path remains [3], target 4. Recurse to index 3.

💡 Skipping candidate 6 to try candidate 7 next.

Line:

for count in range(max_use + 1):
    backtrack(...)

💡 The algorithm tries skipping candidates to find all combinations.

choose

Try using candidate 7 zero times with path [3]

At index 3, try count = 0, path remains [3], target 4. Recurse to index 4 (end).

💡 No candidates left to try, target not zero, dead end.

Line:

for count in range(max_use + 1):
    backtrack(...)

💡 No solution found on this path, recursion backtracks.

choose

Backtrack to index 1, try using candidate 3 two times

At index 1, try count = 2, path becomes [3,3], target reduces to 1. Recurse to index 2.

💡 Trying candidate 3 multiple times to build sums closer to target.

Line:

backtrack(index + 1, path + [candidates[index]] * count, target - candidates[index] * count)

💡 The algorithm tries all counts up to max possible for each candidate.

choose

Try using candidate 6 zero times with path [3,3]

At index 2, try count = 0, path remains [3,3], target 1. Recurse to index 3.

💡 Skipping candidate 6 to try candidate 7 next.

Line:

for count in range(max_use + 1):
    backtrack(...)

💡 The algorithm continues exploring all branches systematically.

choose

Try using candidate 7 zero times with path [3,3]

At index 3, try count = 0, path remains [3,3], target 1. Recurse to index 4 (end).

💡 No candidates left, target not zero, dead end reached.

Line:

for count in range(max_use + 1):
    backtrack(...)

💡 No solution found here, recursion backtracks.

choose

Backtrack to index 0, try using candidate 2 one time

At index 0, try count = 1, path becomes [2], target reduces to 5. Recurse to index 1.

💡 Trying candidate 2 once to build partial sums.

Line:

backtrack(index + 1, path + [candidates[index]] * count, target - candidates[index] * count)

💡 The algorithm explores new partial combinations including candidate 2.

choose

Try using candidate 3 zero times with path [2]

At index 1, try count = 0, path remains [2], target 5. Recurse to index 2.

💡 Skipping candidate 3 to try candidate 6 next.

Line:

for count in range(max_use + 1):
    backtrack(...)

💡 The algorithm tries skipping candidates to find all combinations.

choose

Try using candidate 6 zero times with path [2]

At index 2, try count = 0, path remains [2], target 5. Recurse to index 3.

💡 Skipping candidate 6 to try candidate 7 next.

Line:

for count in range(max_use + 1):
    backtrack(...)

💡 The algorithm continues exploring all branches systematically.

choose

Try using candidate 7 zero times with path [2]

At index 3, try count = 0, path remains [2], target 5. Recurse to index 4 (end).

💡 No candidates left, target not zero, dead end reached.

Line:

for count in range(max_use + 1):
    backtrack(...)

💡 No solution found here, recursion backtracks.

choose

Try using candidate 2 two times and candidate 3 one time to reach target

Back at index 0, try count = 2 for candidate 2, path becomes [2,2], target reduces to 3. Then at index 1, try count = 1 for candidate 3, path becomes [2,2,3], target reduces to 0. Valid combination found.

💡 Combining multiple counts of candidates to exactly reach the target.

Line:

backtrack(index + 1, path + [candidates[index]] * count, target - candidates[index] * count)

💡 The algorithm finds the combination [2,2,3] that sums to target.

from typing import List

def combinationSum(candidates: List[int], target: int) -> List[List[int]]:
    candidates.sort()  # STEP 1
    result = []
    def backtrack(index, path, target):
        if target == 0:  # STEP when valid combination found
            result.append(path[:])  # STEP record answer
            return
        if index == len(candidates) or target < 0:  # STEP prune invalid path
            return
        max_use = target // candidates[index]  # STEP compute max count
        for count in range(max_use + 1):  # STEP try counts 0..max_use
            backtrack(index + 1, path + [candidates[index]] * count, target - candidates[index] * count)  # STEP recurse
    backtrack(0, [], target)  # STEP initial call
    return result

if __name__ == '__main__':
    print(combinationSum([2,3,6,7], 7))  # STEP run example

📊

Combination Sum (Reuse Allowed) - Watch the Algorithm Execute, Step by Step

Watching this step-by-step recursion tree helps you understand how the algorithm systematically builds combinations and prunes impossible paths, which is hard to grasp from code alone.

enteringindex=0path=[]target=7

Call Path (current → root)

backtrack(0, [], 7)

Remaining

count=0 to 3 for candidate 2

enteringindex=1path=[]target=7

Call Path (current → root)

backtrack(1, [], 7)

backtrack(0, [], 7)

Remaining

count=0 to 2 for candidate 3

enteringindex=2path=[]target=7

Call Path (current → root)

backtrack(2, [], 7)

backtrack(1, [], 7)

backtrack(0, [], 7)

Remaining

count=0 to 1 for candidate 6

enteringindex=3path=[]target=7

Call Path (current → root)

backtrack(3, [], 7)

backtrack(2, [], 7)

backtrack(1, [], 7)

backtrack(0, [], 7)

Remaining

count=0 to 1 for candidate 7

backtrackingindex=4path=[]target=7

Call Path (current → root)

backtrack(4, [], 7)

backtrack(3, [], 7)

backtrack(2, [], 7)

backtrack(1, [], 7)

backtrack(0, [], 7)

✂ index == len(candidates)

enteringindex=4path=[7]target=0

Call Path (current → root)

backtrack(4, [7], 0)

backtrack(3, [], 7)

backtrack(2, [], 7)

backtrack(1, [], 7)

backtrack(0, [], 7)

Partial: [7]

Found 1: [7]

choosingindex=2path=[]target=7

Call Path (current → root)

backtrack(2, [], 7)

backtrack(1, [], 7)

backtrack(0, [], 7)

Tried

count=0

Remaining

count=1 for candidate 6

Found 1: [7]

enteringindex=3path=[6]target=1

Call Path (current → root)

backtrack(3, [6], 1)

backtrack(2, [6], 1)

backtrack(1, [], 7)

backtrack(0, [], 7)

Remaining

count=0 to 0 for candidate 7

Partial: [6]

Found 1: [7]

backtrackingindex=4path=[6]target=1

Call Path (current → root)

backtrack(4, [6], 1)

backtrack(3, [6], 1)

backtrack(2, [6], 1)

backtrack(1, [], 7)

backtrack(0, [], 7)

Partial: [6]

✂ index == len(candidates)

Found 1: [7]

enteringindex=2path=[3]target=4

Call Path (current → root)

backtrack(2, [3], 4)

backtrack(1, [3], 4)

backtrack(0, [], 7)

Remaining

count=0 to 0 for candidate 6

Partial: [3]

Found 1: [7]

enteringindex=3path=[3]target=4

Call Path (current → root)

backtrack(3, [3], 4)

backtrack(2, [3], 4)

backtrack(1, [3], 4)

backtrack(0, [], 7)

Remaining

count=0 to 0 for candidate 7

Partial: [3]

Found 1: [7]

backtrackingindex=4path=[3]target=4

Call Path (current → root)

backtrack(4, [3], 4)

backtrack(3, [3], 4)

backtrack(2, [3], 4)

backtrack(1, [3], 4)

backtrack(0, [], 7)

Partial: [3]

✂ index == len(candidates)

Found 1: [7]

enteringindex=2path=[3,3]target=1

Call Path (current → root)

backtrack(2, [3, 3], 1)

backtrack(1, [3, 3], 1)

backtrack(0, [], 7)

Remaining

count=0 to 0 for candidate 6

Partial: [3, 3]

Found 1: [7]

enteringindex=3path=[3,3]target=1

Call Path (current → root)

backtrack(3, [3, 3], 1)

backtrack(2, [3, 3], 1)

backtrack(1, [3, 3], 1)

backtrack(0, [], 7)

Remaining

count=0 to 0 for candidate 7

Partial: [3, 3]

Found 1: [7]

backtrackingindex=4path=[3,3]target=1

Call Path (current → root)

backtrack(4, [3, 3], 1)

backtrack(3, [3, 3], 1)

backtrack(2, [3, 3], 1)

backtrack(1, [3, 3], 1)

backtrack(0, [], 7)

Partial: [3, 3]

✂ index == len(candidates)

Found 1: [7]

enteringindex=1path=[2]target=5

Call Path (current → root)

backtrack(1, [2], 5)

backtrack(0, [], 7)

Remaining

count=0 to 1 for candidate 3

Partial: [2]

Found 1: [7]

enteringindex=2path=[2]target=5

Call Path (current → root)

backtrack(2, [2], 5)

backtrack(1, [2], 5)

backtrack(0, [], 7)

Remaining

count=0 to 0 for candidate 6

Partial: [2]

Found 1: [7]

enteringindex=3path=[2]target=5

Call Path (current → root)

backtrack(3, [2], 5)

backtrack(2, [2], 5)

backtrack(1, [2], 5)

backtrack(0, [], 7)

Remaining

count=0 to 0 for candidate 7

Partial: [2]

Found 1: [7]

backtrackingindex=4path=[2]target=5

Call Path (current → root)

backtrack(4, [2], 5)

backtrack(3, [2], 5)

backtrack(2, [2], 5)

backtrack(1, [2], 5)

backtrack(0, [], 7)

Partial: [2]

✂ index == len(candidates)

Found 1: [7]

enteringindex=2path=[2,2,3]target=0

Call Path (current → root)

backtrack(2, [2, 2, 3], 0)

backtrack(1, [2, 2], 3)

backtrack(0, [], 7)

Partial: [2, 2, 3]

Found 2: [7] [2,2,3]

Key Takeaways

✓ Backtracking tries all counts of each candidate systematically, ensuring no duplicates and complete coverage.

This exhaustive approach is hard to visualize from code alone but clear when watching the recursion tree.

✓ Sorting candidates and moving forward in index prevents duplicate combinations and keeps results ordered.

Understanding this ordering is key to grasping why the algorithm avoids repeated permutations.

✓ Pruning occurs when target < 0 or index exceeds candidates, which stops useless exploration early.

Seeing pruning in action helps understand efficiency gains in backtracking.

Practice

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

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

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

4. Examine the following buggy code snippet for partitioning an array into k equal sum subsets using backtracking with bitmask memoization. Which line contains the subtle bug that can cause incorrect results or inefficiency?

medium

A. Line 2: missing check if total is divisible by k

B. Line 6: sorting nums in descending order

C. Line 14: memoizing result after recursive call

D. Line 18: checking if element is unused and fits in current subset

Solution

1. Step 1: Identify missing early pruning

   Line 2 calculates total but does not check if total % k != 0, which is critical to avoid futile search.

2. Step 2: Verify other lines

   Sorting descending (line 6) is correct for pruning; memoization (line 14) and usage check (line 18) are correct.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Without divisibility check, algorithm wastes time exploring impossible partitions [OK]

Hint: Always check divisibility before backtracking [OK]

Common Mistakes:

• Forgetting early divisibility check
• Misplacing memoization

5. Suppose the problem changes: now you can use each element in the array unlimited times to form subsets summing to K (i.e., unlimited repetitions allowed). Which modification to the space-optimized DP code below correctly counts the number of such subsets?

def count_subsets_unlimited(arr, K):
    dp = [0] * (K + 1)
    dp[0] = 1
    for num in arr:
        for j in range(???):
            dp[j] += dp[j - num]
    return dp[K]

Choose the correct range for the inner loop to handle unlimited usage of elements.

hard

A. for j in range(K, num - 1, -1): # iterate backward

B. for j in range(K + 1): # iterate forward including invalid indices

C. for j in range(0, K + 1): # iterate forward from 0

D. for j in range(num, K + 1): # iterate forward

Solution

1. Step 1: Understand unlimited usage impact

   When elements can be reused unlimited times, the inner loop must iterate forward to allow multiple counts of the same element.

2. Step 2: Choose correct iteration range

   Iterating forward from num to K ensures dp[j] accumulates counts including repeated usage of num.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Forward iteration enables unlimited reuse of elements in subset sums [OK]

Hint: Unlimited usage requires forward iteration to accumulate counts correctly [OK]

Common Mistakes:

• Using backward iteration which prevents reuse
• Starting loop from 0 causing invalid indices