Why Backtracking and What Greedy Cannot Solve in DSA Typescript - Challenge Your Understanding

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Backtracking Subset Sum

What is the output of the following TypeScript code that uses backtracking to find subsets summing to 5?

DSA Typescript

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

const nums = [1, 2, 3, 4];
const res: number[][] = [];
backtrack(nums, 5, 0, [], res);
console.log(res);

A [[1,2,3],[1,4],[2,3]]

B [[1,4],[2,3]]

C [[1,4],[2,3],[5]]

D [[1,2,3,4]]

💡 Hint

Think about which combinations of numbers add exactly to 5 without repetition.

The backtracking function finds all unique subsets of nums that sum to 5. The valid subsets are [1,4] and [2,3]. The subset [1,2,3] sums to 6, so it's invalid. The number 5 is not in the list, so [5] is invalid. The full list sums to 10, so [1,2,3,4] is invalid.

🧠 Conceptual

intermediate

Why Greedy Fails for Subset Sum

Why does a greedy algorithm fail to solve the subset sum problem correctly in all cases?

A Because greedy algorithms make local optimal choices that may miss the correct subset sum.

B Because greedy algorithms always find the global optimum by checking all subsets.

C Because greedy algorithms use backtracking to explore all possibilities.

D Because greedy algorithms sort the input and always find the correct subset.

💡 Hint

Think about how greedy algorithms decide step-by-step without revisiting choices.

Greedy algorithms pick the best immediate option without considering future consequences. This can cause them to miss subsets that sum to the target because they don't explore all combinations.

❓ Predict Output

advanced

Backtracking vs Greedy Output Comparison

What is the output of the following TypeScript code comparing greedy and backtracking approaches for target sum 7?

DSA Typescript

function greedy(nums: number[], target: number): number[] {
  const res: number[] = [];
  let sum = 0;
  for (const num of nums) {
    if (sum + num <= target) {
      res.push(num);
      sum += num;
    }
  }
  return res;
}

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

const nums = [2, 3, 5, 6];
const greedyResult = greedy(nums, 7);
const backtrackResult: number[][] = [];
backtrack(nums, 7, 0, [], backtrackResult);
console.log({greedyResult, backtrackResult});

A {"greedyResult":[2,3],"backtrackResult":[[2,5],[3,4]]}

B {"greedyResult":[2,3,5],"backtrackResult":[[2,5],[3,5]]}

C {"greedyResult":[2,3],"backtrackResult":[[2,5]]}

D }]]4,3[,]5,2[[:"tluseRkcartkcab",]3,2[:"tluseRydeerg"{

💡 Hint

Check which subsets sum exactly to 7 and what greedy picks.

The greedy picks 2, then 3, then tries 5 but sum would be 10 > 7, so stops at [2,3]. Backtracking finds [2,5] as the only subset summing to 7. The option with [3,4] is invalid because 4 is not in the list.

🔧 Debug

advanced

Identify the Error in Greedy Algorithm for Coin Change

What error does the following greedy coin change code produce when trying to make change for 6 with coins [1,3,4]?

DSA Typescript

function greedyCoinChange(coins: number[], amount: number): number[] {
  coins.sort((a, b) => b - a);
  const result: number[] = [];
  for (const coin of coins) {
    while (amount >= coin) {
      result.push(coin);
      amount -= coin;
    }
  }
  if (amount !== 0) throw new Error('Cannot make exact change');
  return result;
}

console.log(greedyCoinChange([1,3,4], 6));

A Returns [4,1,1] which sums to 6

B Returns [4,3] which sums to 7

C Returns [3,3] which sums to 6

D Throws 'Cannot make exact change' error

💡 Hint

Check how the greedy picks coins starting from largest.

The greedy picks 4 first, then two 1s to make 6. It returns [4,1,1]. It does not throw error because amount reaches 0. It does not pick [3,3] because 4 is chosen first greedily.

🧠 Conceptual

expert

Why Backtracking is Needed for N-Queens Problem

Why is backtracking necessary to solve the N-Queens problem instead of a greedy approach?

A Because greedy algorithms can place queens anywhere without checking conflicts.

B Because backtracking always places queens in the first row only.

C Because greedy algorithms use recursion to explore all board positions.

D Because greedy algorithms cannot guarantee placing all queens without conflicts by local choices alone.

💡 Hint

Think about how placing one queen affects future placements.

The N-Queens problem requires checking all possible placements to avoid conflicts. Greedy algorithms make local choices that may block future queen placements, so backtracking is needed to explore and undo choices.