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

Time Complexity: Why Backtracking and What Greedy Cannot Solve

O(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.

function backtrack(options, path = []) {
  if (path.length === options.length) {
    console.log(path);
    return;
  }
  for (let i = 0; i < options.length; i++) {
    if (!path.includes(options[i])) {
      path.push(options[i]);
      backtrack(options, path);
      path.pop();
    }
  }
}

backtrack([1, 2, 3]);
    

This code tries all orderings of the given options by exploring every choice step by step.

Identify Repeating Operations

Look at what repeats in this code.

• Primary operation: The for-loop tries each unused option at every step.
• How many times: It repeats for every position in the path, exploring all possible orders.

How Execution Grows With Input

As the number of options grows, the number of paths grows very fast.

Input Size (n)	Approx. Operations
3	6 (3 x 2 x 1)
4	24 (4 x 3 x 2 x 1)
5	120 (5 x 4 x 3 x 2 x 1)

Pattern observation: The operations grow as the factorial of input size, which is much faster than linear or quadratic growth.

Final Time Complexity

Time Complexity: O(n!)

This means the time needed grows very fast because we try every possible order of choices.

Common Mistake

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

[OK] Correct: Greedy picks the best choice at each step without looking ahead, so it can miss better overall solutions that backtracking finds by exploring all options.

Interview Connect

Understanding when to use backtracking versus greedy shows you can choose the right tool for tricky problems, a skill valued in real coding challenges.

Self-Check

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

Practice

1. Why is backtracking preferred over greedy algorithms in problems like the N-Queens puzzle?

easy

A. Because backtracking explores all possible solutions and can undo choices, while greedy makes irreversible decisions.

B. Because greedy algorithms always find the optimal solution faster than backtracking.

C. Because backtracking uses less memory than greedy algorithms.

D. Because greedy algorithms are only used for sorting problems.

Solution

1. Step 1: Understand backtracking's approach

   Backtracking tries all possible options and can go back to previous steps to try different paths.

2. Step 2: Compare with greedy algorithm

   Greedy makes the best immediate choice without reconsidering, which can miss the correct solution in complex problems.

3. Final Answer:

   Because backtracking explores all possible solutions and can undo choices, while greedy makes irreversible decisions. -> Option A

4. Quick Check:

   Backtracking = explores all + undo [OK]

Hint: Backtracking tries all paths; greedy picks immediate best [OK]

Common Mistakes:

• Thinking greedy always finds the best solution
• Confusing memory usage between backtracking and greedy
• Assuming greedy can undo choices

2. Which of the following is the correct syntax to start a backtracking function in JavaScript?

easy

A. function backtrack = (path, options) => { /* code */ }

B. function backtrack(path, options) { /* code */ }

C. backtrack function(path, options) { /* code */ }

D. function backtrack[path, options] { /* code */ }

Solution

1. Step 1: Recall JavaScript function declaration syntax

   Functions are declared using the keyword 'function' followed by the name and parentheses with parameters.

2. Step 2: Check each option

   function backtrack(path, options) { /* code */ } uses correct syntax. function backtrack = (path, options) => { /* code */ } uses incorrect assignment syntax. backtrack function(path, options) { /* code */ } has wrong keyword order. function backtrack[path, options] { /* code */ } uses brackets incorrectly.

3. Final Answer:

   function backtrack(path, options) { /* code */ } -> Option B

4. Quick Check:

   Standard function declaration = function backtrack(path, options) { /* code */ } [OK]

Hint: Use 'function name(params) { }' for normal functions [OK]

Common Mistakes:

• Using '=' with function keyword incorrectly
• Mixing function declaration and expression syntax
• Using brackets [] instead of parentheses ()

3. What will be the output of the following code snippet?

function backtrack(nums, path, res) {
  if (path.length === nums.length) {
    res.push([...path]);
    return;
  }
  for (let i = 0; i < nums.length; i++) {
    if (path.includes(nums[i])) continue;
    path.push(nums[i]);
    backtrack(nums, path, res);
    path.pop();
  }
}

const result = [];
backtrack([1, 2], [], result);
console.log(result);

medium

A. [[1, 2]]

B. [[2, 1]]

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

D. [[1], [2]]

Solution

1. Step 1: Understand the backtracking logic

   The function generates all permutations of the array [1, 2] by adding elements not already in the path.

2. Step 2: Trace the recursive calls

   First path: [1, 2], second path: [2, 1]. Both are added to result.

3. Final Answer:

   [[1, 2], [2, 1]] -> Option C

4. Quick Check:

   Permutations of [1,2] = [[1,2],[2,1]] [OK]

Hint: Backtracking with includes avoids duplicates, generates permutations [OK]

Common Mistakes:

• Forgetting to pop after recursion
• Not checking if element is already in path
• Expecting only one permutation

4. Identify the bug in this backtracking code for generating subsets:

function subsets(nums) {
  const res = [];
  function backtrack(start, path) {
    res.push(path);
    for (let i = start; i < nums.length; i++) {
      path.push(nums[i]);
      backtrack(i + 1, path);
      path.pop();
    }
  }
  backtrack(0, []);
  return res;
}

medium

A. The function should return inside the loop.

B. The loop should start from 0 instead of start.

C. The pop() is missing after recursive call.

D. The code pushes the same path array reference, causing all results to be identical.

Solution

1. Step 1: Analyze how path is added to results

   The code pushes 'path' directly, which is a reference to the same array that changes over time.

2. Step 2: Understand consequences

   All entries in res will point to the same array, resulting in identical subsets at the end.

3. Final Answer:

   The code pushes the same path array reference, causing all results to be identical. -> Option D

4. Quick Check:

   Push copy of path, not reference [OK]

Hint: Push a copy of path (e.g., [...path]) to avoid reference bugs [OK]

Common Mistakes:

• Pushing path without copying
• Incorrect loop start index
• Missing pop after recursion

5. Given the problem of selecting a subset of items with weights and values to maximize value without exceeding weight limit, why can't a greedy algorithm always solve it correctly, and how does backtracking help?

Choose the best explanation.

hard

A. Greedy picks items with highest value first, which may exceed weight; backtracking tries all combinations to find the best fit.

B. Greedy always finds the best solution by sorting items by weight; backtracking is slower and unnecessary.

C. Greedy picks items randomly; backtracking sorts items before selection.

D. Greedy and backtracking both always find the same solution for this problem.

Solution

1. Step 1: Understand greedy approach limitations

   Greedy selects items based on immediate criteria (like highest value), which can lead to overweight or suboptimal total value.

2. Step 2: Understand backtracking advantage

   Backtracking explores all subsets, checking weight limits and total values, ensuring the optimal subset is found.

3. Final Answer:

   Greedy picks items with highest value first, which may exceed weight; backtracking tries all combinations to find the best fit. -> Option A

4. Quick Check:

   Greedy = local best, Backtracking = global best [OK]

Hint: Greedy fails on constraints; backtracking tries all combos [OK]

Common Mistakes:

• Assuming greedy always works for knapsack
• Thinking backtracking is always slower without benefit
• Confusing sorting criteria in greedy