Why Backtracking and What Greedy Cannot Solve in DSA Typescript - Performance Analysis

Time Complexity: Why Backtracking and What Greedy Cannot Solve

O(2^n)

Understanding Time Complexity

We want to understand why some problems need backtracking instead of greedy methods.

How does the time needed grow when we try all possibilities versus making quick choices?

Scenario Under Consideration

Analyze the time complexity of this backtracking example for subset sum.

function subsetSum(nums: number[], target: number, index = 0): boolean {
  if (target === 0) return true;
  if (index === nums.length || target < 0) return false;
  // Choose current number
  if (subsetSum(nums, target - nums[index], index + 1)) return true;
  // Skip current number
  return subsetSum(nums, target, index + 1);
}
    

This code tries all combinations of numbers to find if any sum to the target.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Recursive calls exploring two choices at each step.
• How many times: Up to 2 calls per element, leading to many combinations.

How Execution Grows With Input

Each number doubles the possible combinations to check.

Input Size (n)	Approx. Operations
10	About 1,024 calls
20	About 1,048,576 calls
30	About 1,073,741,824 calls

Pattern observation: Operations grow exponentially as input size increases.

Final Time Complexity

Time Complexity: O(2^n)

This means the time doubles with each extra element, making it slow for large inputs.

Common Mistake

[X] Wrong: "Greedy choices always find the best solution quickly."

[OK] Correct: Greedy methods pick locally best steps but can miss the overall best answer, especially when choices depend on future options.

Interview Connect

Understanding when to use backtracking versus greedy shows your problem-solving depth and helps you choose the right tool for complex problems.

Self-Check

What if we added memoization to this backtracking? How would the time complexity change?