Generate All Combinations Sum K in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of combinations summing to K

What is the output of the following code that generates all combinations of numbers from 1 to 4 that sum to 5?

DSA Python

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

print(comb_sum_k(4, 5))

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

B [[1, 2, 2], [1, 4], [2, 3]]

C [[5]]

D [[1, 4], [2, 3]]

💡 Hint

Think about how the backtracking avoids duplicates and only uses numbers once.

The code generates combinations of unique numbers from 1 to 4 that sum to 5. Only [1,4] and [2,3] satisfy this with unique numbers and no repeats.

❓ Predict Output

intermediate

Number of combinations summing to K

How many unique combinations of numbers from 1 to 5 sum to 7 using the code below?

DSA Python

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

print(len(comb_sum_k(5, 7)))

A 3

B 5

C 4

D 6

💡 Hint

List out all combinations manually or think about subsets of 1 to 5 that sum to 7.

The valid combinations are [1,2,4], [2,5], [3,4]. Total of 3 combinations.

🔧 Debug

advanced

Identify the error in combination sum code

What error does the following code raise when trying to generate combinations summing to 4?

DSA Python

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

print(comb_sum_k(4, 4))

A IndexError

B Missing combinations due to range end

C TypeError

D No error, outputs [[1,3], [4]]

💡 Hint

Check the range used in the for loop and if it includes the last number.

The for loop uses range(start, n) which excludes n. So number n is never included, missing combinations with n.

🧠 Conceptual

advanced

Why use backtracking for combination sum?

Why is backtracking a suitable approach to generate all combinations of numbers summing to K?

A Because it uses dynamic programming to store intermediate results

B Because it sorts the input numbers automatically

C Because it explores all possible subsets efficiently by pruning invalid paths early

D Because it only generates combinations with repeated numbers

💡 Hint

Think about how backtracking avoids unnecessary work.

Backtracking tries all possible combinations but stops exploring a path as soon as the sum exceeds K, saving time.

🚀 Application

expert

Find all combinations summing to K with duplicates allowed

Modify the code to allow repeated numbers in combinations summing to K from 1 to 3. What is the output for K=4?

DSA Python

def comb_sum_k_with_repeats(n, k):
    result = []
    def backtrack(start, path, total):
        if total == k:
            result.append(path[:])
            return
        if total > k:
            return
        for i in range(start, n+1):
            path.append(i)
            backtrack(i, path, total + i)  # allow repeats by not increasing start
            path.pop()
    backtrack(1, [], 0)
    return result

print(comb_sum_k_with_repeats(3, 4))

A [[1,1,1,1], [1,1,2], [1,3], [2,2]]

B [[1,1,1,1], [1,1,2], [1,3], [2,2], [3,1]]

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

D [[1,1,1,1], [1,1,2], [1,3], [2,2], [3,1], [4]]

💡 Hint

Allow repeats by calling backtrack with same start index.

The code allows repeats by calling backtrack with the same start index (backtrack(i, ...)). It generates non-decreasing combinations: [[1,1,1,1], [1,1,2], [1,3], [2,2]].

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