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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Backtracking Subset Sum

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

DSA C++

#include <iostream>
#include <vector>
using namespace std;

void backtrack(vector<int>& nums, int target, int start, vector<int>& current, vector<vector<int>>& result) {
    if (target == 0) {
        for (int num : current) cout << num << " ";
        cout << "| ";
        return;
    }
    for (int i = start; i < nums.size(); i++) {
        if (nums[i] <= target) {
            current.push_back(nums[i]);
            backtrack(nums, target - nums[i], i + 1, current, result);
            current.pop_back();
        }
    }
}

int main() {
    vector<int> nums = {1, 2, 3, 4, 5};
    vector<int> current;
    vector<vector<int>> result;
    backtrack(nums, 5, 0, current, result);
    return 0;
}

A 1 2 3 4 5 |

B 5 | 1 2 3 | 2 4 |

C 1 4 | 2 3 | 5 |

D No output

💡 Hint

Think about all subsets of nums that add up exactly to 5 without reuse.

The code finds all subsets of the array {1,2,3,4,5} that sum to 5 using backtracking. The valid subsets are {1,4}, {2,3}, and {5}.

🧠 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 picks local best choices that may not lead to global solution

B Because greedy always tries all subsets which is inefficient

C Because greedy requires sorting which is impossible for subset sum

D Because greedy uses backtracking internally

💡 Hint

Consider if picking the largest number first always leads to a correct subset sum.

Greedy algorithms make the best local choice at each step but may miss the correct combination that requires skipping a local best choice.

🔧 Debug

advanced

Identify the Error in Greedy Coin Change

What error does the following greedy coin change code produce when given coins {1,3,4} and amount 6?

DSA C++

#include <iostream>
#include <vector>
using namespace std;

int greedyCoinChange(vector<int>& coins, int amount) {
    int count = 0;
    for (int i = coins.size() - 1; i >= 0; i--) {
        while (amount >= coins[i]) {
            amount -= coins[i];
            count++;
        }
    }
    return amount == 0 ? count : -1;
}

int main() {
    vector<int> coins = {1, 3, 4};
    cout << greedyCoinChange(coins, 6);
    return 0;
}

A Returns -1 indicating no solution

B Returns 3 (coins 4 + 1 + 1) which is incorrect minimum

C Returns 3 (coins 3 + 3) which is correct minimum

D Compilation error due to missing headers

💡 Hint

Check how greedy picks coins starting from largest coin.

The greedy picks coin 4 first, then two coins of 1, total 3 coins, but minimum coins needed is 2 (3+3). So output is 3 which is incorrect.

❓ Predict Output

advanced

Backtracking N-Queens Output Count

What is the output count of solutions printed by this backtracking code for N=4?

DSA C++

#include <iostream>
#include <vector>
using namespace std;

bool isSafe(vector<int>& board, int row, int col) {
    for (int i = 0; i < row; i++) {
        if (board[i] == col || abs(board[i] - col) == row - i) return false;
    }
    return true;
}

void solveNQueens(int n, int row, vector<int>& board, int& count) {
    if (row == n) {
        count++;
        return;
    }
    for (int col = 0; col < n; col++) {
        if (isSafe(board, row, col)) {
            board[row] = col;
            solveNQueens(n, row + 1, board, count);
        }
    }
}

int main() {
    int n = 4;
    vector<int> board(n);
    int count = 0;
    solveNQueens(n, 0, board, count);
    cout << count;
    return 0;
}

A 0

B 4

C 1

D 2

💡 Hint

N-Queens for 4 has exactly 2 solutions.

The classic 4-Queens problem has 2 distinct solutions found by backtracking.

🧠 Conceptual

expert

Why Backtracking is Needed Over Greedy for Hamiltonian Path

Why is backtracking necessary to find a Hamiltonian path in a graph instead of a greedy approach?

A Because greedy cannot guarantee visiting all vertices exactly once in complex graphs

B Because greedy always finds the shortest path which is not Hamiltonian

C Because greedy requires sorting vertices which is impossible in graphs

D Because backtracking uses dynamic programming internally

💡 Hint

Think about the complexity of visiting all nodes exactly once.

Greedy algorithms make local choices and cannot ensure a path visiting all vertices exactly once, which requires exploring all possibilities via backtracking.

Practice

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

easy

A. Because backtracking uses less memory than greedy algorithms

B. Because greedy algorithms always find the optimal solution quickly

C. Because backtracking explores all possible solutions and can backtrack on wrong choices

D. Because greedy algorithms do not use recursion

Solution

1. Step 1: Understand problem requirements

   The N-Queens puzzle requires placing queens so none attack each other, needing exploration of many possibilities.

2. Step 2: Compare algorithm approaches

   Backtracking tries all options and reverses wrong choices, while greedy picks immediate best without reconsidering.

3. Final Answer:

   Because backtracking explores all possible solutions and can backtrack on wrong choices -> Option C

4. Quick Check:

   Backtracking explores all options = A [OK]

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

Common Mistakes:

• Thinking greedy always finds the best solution
• Confusing memory usage between algorithms
• Assuming backtracking is always slower

2. Which of the following is the correct syntax to start a backtracking function in C++ for solving a subset sum problem?

easy

A. int backtrack(vector<int> nums, int sum) { }

B. void backtrack(int index, int currentSum, vector<int>& nums) { }

C. void backtrack(int sum, int index) { }

D. bool backtrack(int currentSum, vector<int> nums) { }

Solution

1. Step 1: Identify typical backtracking parameters

   Backtracking usually tracks current index, current sum, and the input list by reference for efficiency.

2. Step 2: Check each option's parameter order and types

   void backtrack(int index, int currentSum, vector<int>& nums) { } correctly uses index, currentSum, and reference to vector; others have wrong order or pass by value unnecessarily.

3. Final Answer:

   void backtrack(int index, int currentSum, vector<int>& nums) { } -> Option B

4. Quick Check:

   Correct parameter order and reference = B [OK]

Hint: Backtracking needs index, current state, and reference input [OK]

Common Mistakes:

• Passing vector by value causing inefficiency
• Wrong parameter order
• Using incorrect return type for backtracking

3. What will be the output of the following C++ code snippet that uses backtracking to print all subsets of {1, 2}?

void backtrack(int i, vector<int>& nums, vector<int>& subset) {
    if (i == nums.size()) {
        for (int x : subset) cout << x << " ";
        cout << "| ";
        return;
    }
    subset.push_back(nums[i]);
    backtrack(i + 1, nums, subset);
    subset.pop_back();
    backtrack(i + 1, nums, subset);
}

int main() {
    vector<int> nums = {1, 2};
    vector<int> subset;
    backtrack(0, nums, subset);
    return 0;
}

medium

A. 1 2 | 1 | 2 | |

B. 1 2 | 2 | 1 | |

C. 1 2 | 1 | | 2 |

D. | 1 | 2 | 1 2 |

Solution

1. Step 1: Trace recursive calls with subset additions

   First call adds 1 and 2, prints "1 2 | ". Then backtracks to remove 2, prints "1 | ". Then removes 1, adds 2, prints "2 | ". Finally prints empty subset "| ".

2. Step 2: Confirm output order matches 1 2 | 1 | 2 | |

   Output order is "1 2 | 1 | 2 | | ", matching 1 2 | 1 | 2 | | exactly.

3. Final Answer:

   1 2 | 1 | 2 | | -> Option A

4. Quick Check:

   All subsets printed in order = D [OK]

Hint: Backtracking prints subsets by including/excluding elements [OK]

Common Mistakes:

• Mixing order of subset outputs
• Forgetting to pop elements after recursion
• Confusing subset print format

4. Identify the bug in this backtracking code snippet for generating permutations of {1, 2}:

void permute(vector<int>& nums, int start) {
    if (start == nums.size()) {
        for (int x : nums) cout << x << " ";
        cout << "\n";
        return;
    }
    for (int i = start; i < nums.size(); i++) {
        swap(nums[start], nums[i]);
        permute(nums, start + 1);
    }
}

medium

A. Loop should start from 0 instead of start

B. Incorrect base case condition

C. Function should return int instead of void

D. Missing swap(nums[start], nums[i]) to revert after recursion

Solution

1. Step 1: Analyze swap usage in recursion

   Swapping elements before recursion changes order, but must be reverted after to restore original state.

2. Step 2: Identify missing revert swap

   Code swaps but never swaps back after recursive call, causing incorrect permutations.

3. Final Answer:

   Missing swap(nums[start], nums[i]) to revert after recursion -> Option D

4. Quick Check:

   Swap must be reverted after recursion = C [OK]

Hint: Always revert swaps after recursive calls in permutations [OK]

Common Mistakes:

• Not swapping back after recursion
• Wrong base case check
• Incorrect loop range

5. Given the coin denominations {1, 3, 4} and a target sum 6, why does a greedy algorithm fail to find the minimum number of coins, and how does backtracking solve it?

hard

A. Greedy picks largest coin first (4), then 1+1, total 3 coins; backtracking tries all combos and finds 2 coins (3+3)

B. Greedy always finds minimum coins; backtracking is slower but same result

C. Greedy picks smallest coins first; backtracking picks largest coins first

D. Greedy and backtracking both fail for this input

Solution

1. Step 1: Understand greedy approach on coin change

   Greedy picks largest coin <= target repeatedly: picks 4, then two 1s, total 3 coins.

2. Step 2: Understand backtracking approach

   Backtracking tries all combinations, finds 3+3 = 6 with 2 coins, which is fewer than greedy's 3 coins.

3. Final Answer:

   Greedy picks largest coin first (4), then 1+1, total 3 coins; backtracking tries all combos and finds 2 coins (3+3) -> Option A

4. Quick Check:

   Greedy fails minimum coins; backtracking finds optimal = A [OK]

Hint: Greedy may miss combos; backtracking tries all [OK]

Common Mistakes:

• Assuming greedy always optimal
• Confusing coin picking order
• Ignoring backtracking's exhaustive search