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. Consider the following code snippet for counting max bitwise-OR subsets. What is the returned value when input is [1, 2, 3]?

from typing import List

class Solution:
    def countMaxOrSubsets(self, nums: List[int]) -> int:
        n = len(nums)
        max_or = 0
        count = 0
        for mask in range(1, 1 << n):
            current_or = 0
            for i in range(n):
                if mask & (1 << i):
                    current_or |= nums[i]
            if current_or > max_or:
                max_or = current_or
                count = 1
            elif current_or == max_or:
                count += 1
        return count

sol = Solution()
print(sol.countMaxOrSubsets([1, 2, 3]))

easy

A. 5

B. 4

C. 3

D. 6

Solution

1. Step 1: Enumerate all non-empty subsets and their OR

   Subsets: {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3} with ORs 1, 2, 3, 3, 3, 3, 3 respectively.

2. Step 2: Identify max OR and count subsets with that OR

   Max OR is 3; subsets with OR=3 are {3}, {1,2}, {1,3}, {2,3}, {1,2,3} -> 5 subsets.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Counted 5 subsets with max OR 3 -> matches 5 [OK]

Hint: Count subsets with OR equal to max OR -> 5 [OK]

Common Mistakes:

• Counting empty subset as valid
• Miscounting subsets with max OR

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

3. The following code attempts to count subsets with sum K using space-optimized DP. Identify the line that contains a subtle bug that can cause incorrect results.

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

medium

A. for j in range(num, K + 1):

B. dp[0] = 1

C. dp = [0] * (K + 1)

D. dp[j] += dp[j - num]

Solution

1. Step 1: Analyze iteration order

   The inner loop iterates forward from num to K, which causes dp[j] to use updated dp values from the same iteration, leading to overcounting.

2. Step 2: Correct iteration direction

   To avoid overcounting, the inner loop must iterate backward from K down to num.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Forward iteration in DP causes incorrect counts -> bug in loop range [OK]

Hint: Inner loop must iterate backward to avoid reuse of updated dp values [OK]

Common Mistakes:

• Using forward iteration in space-optimized DP
• Misunderstanding dp update dependencies

4. Suppose the problem is modified so that elements can be reused multiple times in the subset (i.e., the subset can contain duplicates). Which modification to the algorithm is necessary to correctly find the largest divisible subset under this new constraint?

hard

A. Modify DP to consider all previous elements including i itself, allowing repeated use, and remove early break

B. Switch to a graph cycle detection algorithm to handle repeated elements

C. Use the same DP approach but allow dp[i] to consider dp[i] itself for reuse, enabling cycles

D. Use a greedy approach picking the largest element repeatedly until no more divisible

Solution

1. Step 1: Understand reuse impact

   Allowing reuse means elements can appear multiple times, so dp must consider extending from the same element multiple times.

2. Step 2: Modify DP logic

   DP inner loop must consider j ≤ i (including i itself) and remove early break because sorted order no longer guarantees divisibility breaks.

3. Step 3: Reject incorrect options

   Greedy fails to find longest chain; graph cycle detection is unnecessary; naive DP without modification misses reuse.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   DP adjusted for reuse and no early break handles duplicates [OK]

Hint: Reuse requires DP to consider self and no early break [OK]

Common Mistakes:

• Using original DP without changes leads to incorrect results
• Trying greedy approach which fails on complex divisibility
• Confusing graph cycles with DP chains

5. If the problem changes to generating all subsets where elements can be reused unlimited times (i.e., multisets), which modification to the iterative approach correctly generates all such subsets?

hard

A. Use backtracking with recursion allowing repeated picks of the same element

B. For each num, append it to existing subsets multiple times until no new subsets are formed

C. Use the same iterative approach but iterate over nums multiple times without resetting result

D. For each num, for each subset in result, append subset + [num] and also keep subset unchanged, repeat for all nums

Solution

1. Step 1: Understand reuse requirement

   Allowing unlimited reuse means subsets can have repeated elements, unlike original subsets.

2. Step 2: Analyze iterative approach limitations

   Iterative approach as-is only adds each num once per subset; it cannot generate repeated elements subsets correctly.

3. Step 3: Identify correct approach

   Backtracking with recursion that allows repeated picks of the same element correctly generates all multisets.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Backtracking naturally supports repeated element choices [OK]

Hint: Backtracking handles repeated elements naturally [OK]

Common Mistakes:

• Trying to reuse iterative approach without modification
• Infinite loops by naive iteration
• Ignoring repeated picks in subsets