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

Time Complexity: Generate All Combinations Sum K

O(2^n * k)

Understanding Time Complexity

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

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

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function combinationSumK(nums: number[], k: number): number[][] {
  const result: number[][] = [];
  function backtrack(start: number, target: number, path: number[]) {
    if (target === 0) {
      result.push([...path]);
      return;
    }
    for (let i = start; i < nums.length; i++) {
      if (nums[i] > target) continue;
      path.push(nums[i]);
      backtrack(i + 1, target - nums[i], path);
      path.pop();
    }
  }
  backtrack(0, k, []);
  return result;
}
    

This code finds all unique combinations of numbers from the array 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 target.

How Execution Grows With Input

As input size grows, the number of possible combinations grows very fast.

Input Size (n)	Approx. Operations
10	Up to thousands of recursive calls
20	Up to millions of recursive calls
30	Potentially billions of recursive calls

Pattern observation: The work grows exponentially because each number can be chosen or skipped, creating many combinations.

Final Time Complexity

Time Complexity: O(2^n * k)

This means the time needed can double with each additional number, as all subsets might be explored, and each valid combination can take up to O(k) time to copy.

Common Mistake

[X] Wrong: "The time grows linearly with the input size because we just loop through the array once."

[OK] Correct: The code uses recursion to explore many combinations, not just a single loop, so the time grows much faster than linear.

Interview Connect

Understanding this helps you explain how recursive solutions explore many possibilities and why some problems need careful time complexity reasoning.

Self-Check

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

Practice

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

easy

A. The count of numbers equal to K

B. The largest number less than K

C. All unique combinations of numbers that add up 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 whose sum equals K.

2. Step 2: Clarify uniqueness and sum condition

   Each combination must sum exactly to K without duplicates in the result.

3. Final Answer:

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

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 sum with count
• Including duplicate combinations
• Looking for single numbers only

2. Which of the following TypeScript function signatures correctly represents a function to generate all combinations summing to K from an array of numbers?

easy

A. function generateCombinations(nums: number, target: number[]): number[]

B. function generateCombinations(nums: number[], target: number): number[][]

C. function generateCombinations(nums: string[], target: string): string[]

D. function generateCombinations(nums: number[], target: number): number[]

Solution

1. Step 1: Analyze parameter types

   The function should take an array of numbers and a target number.

2. Step 2: Analyze return type

   It should return an array of arrays of numbers representing combinations.

3. Final Answer:

   function generateCombinations(nums: number[], target: number): number[][] -> Option B

4. Quick Check:

   Input array and target number, output array of number arrays [OK]

Hint: Input array and target number, output array of arrays [OK]

Common Mistakes:

• Using wrong parameter types
• Returning flat array instead of array of arrays
• Mixing string and number types

3. What is the output of the following TypeScript code?

function combineSum(nums: number[], target: number): number[][] {
  const result: number[][] = [];
  function backtrack(start: number, path: number[], sum: number) {
    if (sum === target) {
      result.push([...path]);
      return;
    }
    if (sum > target) return;
    for (let i = start; i < nums.length; i++) {
      path.push(nums[i]);
      backtrack(i + 1, path, sum + nums[i]);
      path.pop();
    }
  }
  backtrack(0, [], 0);
  return result;
}

console.log(combineSum([1, 2, 3], 3));

medium

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

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

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

D. [[1, 2, 3]]

Solution

1. Step 1: Trace backtracking calls

   Starting from 0, combinations are built adding numbers without reuse: [1,2] sums to 3, [3] sums to 3.

2. Step 2: Confirm valid combinations

   Other combinations like [2] or [1,3] do not sum to 3 or are invalid due to index increment.

3. Final Answer:

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

4. Quick Check:

   Combinations summing to 3 = [[1, 2], [3]] [OK]

Hint: Check sums and index increments carefully [OK]

Common Mistakes:

• Including combinations with reused elements
• Ignoring sum > target condition
• Confusing order of elements

4. Identify the bug in this TypeScript function that aims to generate all combinations summing to K:

function findCombos(nums: number[], target: number): number[][] {
  const res: number[][] = [];
  function dfs(i: number, path: number[], total: number) {
    if (total === target) {
      res.push(path);
      return;
    }
    if (total > target || i === nums.length) return;
    dfs(i + 1, path, total);
    path.push(nums[i]);
    dfs(i + 1, path, total + nums[i]);
    path.pop();
  }
  dfs(0, [], 0);
  return res;
}

medium

A. The function does not return any result

B. The base case does not check for total > target

C. The recursion does not increment index i

D. The path array is pushed by reference causing incorrect results

Solution

1. Step 1: Check how path is stored

   The path array is pushed directly without copying, so later changes affect stored results.

2. Step 2: Understand impact on results

   Because path is referenced, all stored combinations end up empty or incorrect after backtracking.

3. Final Answer:

   The path array is pushed by reference causing incorrect results -> Option D

4. Quick Check:

   Push copy of path, not reference [OK]

Hint: Always push a copy of path, not the original [OK]

Common Mistakes:

• Pushing path without copying
• Not handling base cases properly
• Incorrect index increment

5. Given an array with duplicates, how can you modify the combination sum algorithm to generate all unique combinations summing to K without duplicates in the result?

nums = [1, 2, 2, 3], target = 4

hard

A. Sort the array and skip duplicates during recursion

B. Use a Set to store all combinations as strings

C. Allow duplicates and filter results after generation

D. Ignore duplicates and generate all combinations

Solution

1. Step 1: Sort the input array

   Sorting groups duplicates together, making it easier to skip them during recursion.

2. Step 2: Skip duplicates in recursion

   When iterating, skip elements equal to the previous to avoid duplicate combinations.

3. Final Answer:

   Sort the array and skip duplicates during recursion -> Option A

4. Quick Check:

   Sorting + skipping duplicates = unique combinations [OK]

Hint: Sort and skip duplicates while recursing [OK]

Common Mistakes:

• Not sorting before recursion
• Filtering duplicates after generation (inefficient)
• Ignoring duplicates causing repeated results