Generate All Combinations Sum K in DSA Python

Mental Model

Find all groups of numbers from a list that add up exactly to a target number by trying each number and exploring further choices.

Analogy: Imagine you have a box of different colored beads and want to pick some beads so their total weight equals a specific number. You try picking one bead, then another, and so on, backtracking if the total weight goes over or you run out of beads.

Candidates: [2, 3, 6, 7]
Target: 7
Start -> [] (empty combination)
Try 2 -> [2]
Try 2 again -> [2 -> 2]
Try 3 -> [2 -> 2 -> 3]
Backtrack when sum > 7

Dry Run Walkthrough

Input: candidates: [2, 3, 6, 7], target: 7

Goal: Find all combinations of candidates that sum to 7

Step 1: Start with empty combination [] and target 7

[] (target=7)

Why: We begin with no numbers chosen and full target to reach

Step 2: Pick 2, combination becomes [2], target reduces to 5

[2] (target=5)

Why: Try including 2 and see if we can reach target 7 by adding more

Step 3: Pick 2 again, combination [2 -> 2], target 3

[2 -> 2] (target=3)

Why: We can reuse numbers, so try 2 again to get closer to target

Step 4: Pick 3, combination [2 -> 2 -> 3], target 0

[2 -> 2 -> 3] (target=0)

Why: Sum matches target, record this combination

Step 5: Backtrack to [2 -> 2], try next candidate 6 (too big), backtrack

[2 -> 2] (target=3)

Why: 6 is larger than remaining target, so discard and backtrack

Step 6: Backtrack to [2], try next candidate 3, combination [2 -> 3], target 2

[2 -> 3] (target=2)

Why: Try next candidate after 2 to find other combinations

Step 7: Pick 3 again, combination [2 -> 3 -> 3], target -1 (invalid), backtrack

[2 -> 3] (target=2)

Why: Sum exceeded target, discard and backtrack

Step 8: Backtrack to [], try candidate 3, combination [3], target 4

[3] (target=4)

Why: Try starting with 3 to find other combinations

Step 9: Pick 3 again, combination [3 -> 3], target 1

[3 -> 3] (target=1)

Why: Try reusing 3 to approach target

Step 10: Pick 6 (too big), backtrack to [3], try next candidate 6 (too big), backtrack

[3] (target=4)

Why: 6 is too large, discard and backtrack

Step 11: Backtrack to [], try candidate 6, combination [6], target 1

[6] (target=1)

Why: Try 6 to find combinations

Step 12: Pick 7 (too big), backtrack to [], try 7, combination [7], target 0

[7] (target=0)

Why: 7 matches target exactly, record this combination

Result:

[2 -> 2 -> 3] -> [7]

Annotated Code

DSA Python

from typing import List

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        result = []
        candidates.sort()  # sort to help pruning

        def backtrack(start: int, current_comb: List[int], current_sum: int):
            if current_sum == target:
                result.append(current_comb.copy())  # found valid combination
                return
            if current_sum > target:
                return  # exceed target, stop exploring

            for i in range(start, len(candidates)):
                num = candidates[i]
                # choose num
                current_comb.append(num)
                backtrack(i, current_comb, current_sum + num)  # reuse allowed
                current_comb.pop()  # backtrack

        backtrack(0, [], 0)
        return result

# Driver code
sol = Solution()
candidates = [2, 3, 6, 7]
target = 7
combinations = sol.combinationSum(candidates, target)
for comb in combinations:
    print(' -> '.join(map(str, comb)) + ' -> null')

candidates.sort() # sort to help pruning

sort candidates to try smaller numbers first and prune early

if current_sum == target: result.append(current_comb.copy()) # found valid combination return

record combination when sum matches target exactly

if current_sum > target: return # exceed target, stop exploring

stop exploring when sum exceeds target to save time

for i in range(start, len(candidates)): num = candidates[i] current_comb.append(num) backtrack(i, current_comb, current_sum + num) # reuse allowed current_comb.pop() # backtrack

try each candidate from current position, recurse with updated sum, then backtrack

Output

2 -> 2 -> 3 -> null

7 -> null

Complexity Analysis

Time: O(N^(T/M)) where N is number of candidates, T is target, M is minimum candidate value, because we explore combinations with repetition up to target sum

Space: O(T/M) for recursion stack and current combination storage, proportional to max depth of combination

vs Alternative: Compared to brute force checking all subsets, this approach prunes early and reuses candidates efficiently, reducing unnecessary exploration

Edge Cases

empty candidates list

returns empty list since no combinations possible

DSA Python

for i in range(start, len(candidates)):

target is zero

returns list with empty combination as sum zero is achieved by choosing nothing

DSA Python

if current_sum == target:
    result.append(current_comb.copy())

candidates contain duplicates

duplicates are allowed and can appear multiple times in combinations

DSA Python

for i in range(start, len(candidates)):

When to Use This Pattern

When asked to find all combinations of numbers that sum to a target with possible reuse, use backtracking with pruning to explore choices efficiently.

Common Mistakes

Mistake: Not backtracking properly by forgetting to remove last chosen number after recursion
Fix: Always pop the last number after recursive call to restore state

Mistake: Starting next recursion from i+1 instead of i, disallowing reuse of same candidate
Fix: Start recursion from i to allow reuse of current candidate

Summary

Find all combinations of numbers that add up to a target, allowing repeated use of candidates.

Use when you need every possible group of numbers summing to a value, such as coin change or subset sum variations.

The key is to try each candidate, recurse with updated sum, and backtrack to explore all possibilities.

Practice

1. What does the problem "Generate All Combinations Sum K" ask you to find?

easy

A. All unique combinations of numbers that add up to K

B. The largest number less than K

C. The count of numbers equal to K

D. The smallest number greater than K

Solution

1. Step 1: Understand the problem goal

   The problem asks to find all unique sets of numbers that sum exactly to K.

2. Step 2: Clarify uniqueness and sum condition

   Each combination must add up to K without duplicates in the result.

3. Final Answer:

   All unique combinations of numbers that add up to K -> Option A

4. Quick Check:

   Combinations sum to K = All unique combinations of numbers that add up to K [OK]

Hint: Focus on combinations that sum exactly to K [OK]

Common Mistakes:

• Confusing combinations with permutations
• Looking for single numbers equal to K
• Ignoring the sum condition

2. Which of the following Python function signatures is correct to start solving "Generate All Combinations Sum K"?

easy

A. def combinationSumK(nums, k): return int

B. def combination_sum_k(k: int, nums: list[int]) -> list[int]:

C. def combination_sum_k(nums: int, k: int) -> list[int]:

D. def combination_sum_k(nums: list[int], k: int) -> list[list[int]]:

Solution

1. Step 1: Check parameter types and return type

   The function should take a list of integers and an integer k, returning a list of lists of integers.

2. Step 2: Match signature to problem needs

   def combination_sum_k(nums: list[int], k: int) -> list[list[int]]: matches the expected input and output types correctly.

3. Final Answer:

   def combination_sum_k(nums: list[int], k: int) -> list[list[int]]: -> Option D

4. Quick Check:

   Correct signature with list inputs and list of lists output [OK]

Hint: Use list[int] for input and list[list[int]] for output [OK]

Common Mistakes:

• Wrong parameter types
• Incorrect return type
• Swapping parameter order

3. What is the output of the following code?

def comb_sum(nums, k):
    result = []
    def backtrack(start, path, total):
        if total == k:
            result.append(path[:])
            return
        if total > k:
            return
        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i + 1, path, total + nums[i])
            path.pop()
    backtrack(0, [], 0)
    return result

print(comb_sum([2,3,6,7], 7))

medium

A. [[2, 2, 3]]

B. [[2, 3, 6]]

C. [[7]]

D. [[3, 7]]

Solution

1. Step 1: Trace backtracking with input [2,3,6,7] and target 7

   Check combinations starting from index 0, adding numbers without repetition.

2. Step 2: Identify valid combinations summing to 7

   Only [7] sums exactly to 7 without exceeding or repeating indices.

3. Final Answer:

   [[7]] -> Option C

4. Quick Check:

   Only [7] sums to 7 in given list [OK]

Hint: Backtrack with index increment to avoid duplicates [OK]

Common Mistakes:

• Allowing repeated elements
• Not stopping when total > k
• Appending path without copying

4. Find the error in this code snippet for generating combinations summing to k:

def comb_sum(nums, k):
    result = []
    def backtrack(start, path, total):
        if total == k:
            result.append(path[:])
            return
        if total > k:
            return
        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i, path, total + nums[i])
            path.pop()
    backtrack(0, [], 0)
    return result

medium

A. Appending path without copying causes all results to be the same

B. Using backtrack(i, ...) allows repeated elements incorrectly

C. Missing base case for total < k

D. Not initializing result as a global variable

Solution

1. Step 1: Analyze recursive call backtrack(i, ...)

   Using i instead of i+1 allows reuse of the same element multiple times.

2. Step 2: Understand problem requires unique combinations without repeats

   To avoid duplicates, index must increase to i+1 in recursive calls.

3. Final Answer:

   Using backtrack(i, path, total + nums[i]) allows repeated elements incorrectly -> Option B

4. Quick Check:

   Index must increase to avoid repeats [OK]

Hint: Increment index in recursion to prevent repeats [OK]

Common Mistakes:

• Not copying path when appending
• Allowing repeated elements by wrong index
• Ignoring base cases

5. Given the list [1, 2, 3, 4, 5] and target sum 5, which of the following is the correct set of all unique combinations that sum to 5?

hard

A. [[1, 4], [2, 3], [5]]

B. [[1, 2, 2], [5]]

C. [[1, 1, 3], [2, 3]]

D. [[5, 0], [2, 3]]

Solution

1. Step 1: List all combinations of numbers from [1,2,3,4,5] that sum to 5

   Possible sums: 1+4=5, 2+3=5, 5=5.

2. Step 2: Verify uniqueness and validity

   Combinations like [1,2,2] or [1,1,3] are invalid as 2 or 1 repeated without duplicates allowed.

3. Final Answer:

   [[1, 4], [2, 3], [5]] -> Option A

4. Quick Check:

   Unique combos summing to 5 = [[1, 4], [2, 3], [5]] [OK]

Hint: Sum unique sets without repeating elements [OK]

Common Mistakes:

• Including repeated elements not in input
• Adding zero which is not in list
• Ignoring uniqueness of combinations