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?"