Generate All Combinations Sum K in DSA Python - Time & Space Complexity

Time Complexity: Generate All Combinations Sum K

O(2^n)

Understanding Time Complexity

We want to understand how the time needed to find all combinations that add up to a target number grows as the input size changes.

Specifically, how does the number of possible combinations affect the work done?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

This code finds all unique combinations of numbers from the list that add up exactly to k.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Recursive backtracking exploring combinations.
• How many times: Potentially explores many subsets, depending on input size and values.

How Execution Grows With Input

As the input list grows, the number of possible combinations grows very fast, because each number can be either chosen or not.

Input Size (n)	Approx. Operations
10	Up to 2^10 = 1,024 combinations checked
20	Up to 2^20 = 1,048,576 combinations checked
30	Up to 2^30 = 1,073,741,824 combinations checked

Pattern observation: The work doubles roughly with each additional element, growing exponentially.

Final Time Complexity

Time Complexity: O(2^n)

This means the time needed grows very fast as the input size increases, roughly doubling with each new number.

Common Mistake

[X] Wrong: "The algorithm runs in linear time because it just loops through the list once."

[OK] Correct: The code uses recursion to explore many combinations, not just a single pass, so the work grows exponentially, not linearly.

Interview Connect

Understanding this exponential growth helps you explain why some problems need careful handling and why pruning or sorting can help reduce work.

Self-Check

"What if we allowed numbers to be chosen multiple times? How would the time complexity change?"

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