Why Backtracking and What Greedy Cannot Solve in DSA C++ - Why This Pattern

Mental Model

Backtracking tries all choices step-by-step to find the right answer, while greedy picks the best choice now but can miss the best overall.

Analogy: Imagine choosing a path in a maze: greedy picks the closest exit at each turn but might get stuck; backtracking tries all paths and goes back if stuck.

Start
  ↓
Choice 1 -> Dead end
  ↓
Choice 2 -> Success
Backtracking tries both paths, greedy picks only one.

Dry Run Walkthrough

Input: Set: {1, 3, 4}, Target sum: 6

Goal: Find if any subset sums exactly to 6

Step 1: Try including 1 in subset

Subset: [1], Remaining set: {3,4}, Current sum: 1

Why: Start building subset from first element

Step 2: Try including 3 next

Subset: [1,3], Remaining set: {4}, Current sum: 4

Why: Add next element to get closer to target

Step 3: Try including 4 next

Subset: [1,3,4], Remaining set: {}, Current sum: 8

Why: Sum exceeds target, so backtrack

Step 4: Backtrack: remove 4, try excluding 4

Subset: [1,3], Remaining set: {}, Current sum: 4

Why: Try other option without 4

Step 5: Backtrack: remove 3, try excluding 3 and include 4

Subset: [1,4], Remaining set: {}, Current sum: 5

Why: Try different combination

Step 6: Backtrack: remove 1, try excluding 1 and include 3

Subset: [3], Remaining set: {4}, Current sum: 3

Why: Try subsets without 1

Step 7: Include 4 with 3

Subset: [3,4], Remaining set: {}, Current sum: 7

Why: Sum exceeds target, backtrack

Step 8: Exclude 4, subset is [3], sum 3, no more elements

Subset: [3], Remaining set: {}, Current sum: 3

Why: No solution here, backtrack

Step 9: Try subset with only 4

Subset: [4], Remaining set: {}, Current sum: 4

Why: Try single elements

Step 10: Try subset with 1 and 4 excluded, only 3 included

Subset: [3], Remaining set: {}, Current sum: 3

Why: No solution found yet

Step 11: Try subset with 3 and 4 excluded, only 1 included

Subset: [1], Remaining set: {}, Current sum: 1

Why: No solution found yet

Step 12: Try subset with 1 and 3 excluded, only 4 included

Subset: [4], Remaining set: {}, Current sum: 4

Why: No solution found yet

Step 13: Try subset with 3 and 4 included, sum 7, backtrack

Subset: [3,4], Remaining set: {}, Current sum: 7

Why: Sum too big, backtrack

Step 14: Try subset with 1 and 4 included, sum 5, backtrack

Subset: [1,4], Remaining set: {}, Current sum: 5

Why: Sum less than target, no more elements

Step 15: Try subset with 1 and 3 included, sum 4, backtrack

Subset: [1,3], Remaining set: {}, Current sum: 4

Why: Sum less than target, no more elements

Step 16: Try subset with 3 included only, sum 3, backtrack

Subset: [3], Remaining set: {}, Current sum: 3

Why: Sum less than target, no more elements

Step 17: Try subset with 1 included only, sum 1, backtrack

Subset: [1], Remaining set: {}, Current sum: 1

Why: Sum less than target, no more elements

Step 18: Try subset with 4 included only, sum 4, backtrack

Subset: [4], Remaining set: {}, Current sum: 4

Why: Sum less than target, no more elements

Step 19: Try subset with 3 and 1 included, sum 4, backtrack

Subset: [3,1], Remaining set: {}, Current sum: 4

Why: Sum less than target, no more elements

Step 20: Try subset with 3 and 4 included, sum 7, backtrack

Subset: [3,4], Remaining set: {}, Current sum: 7

Why: Sum too big, backtrack

Step 21: Try subset with 1 and 3 and 4 included, sum 8, backtrack

Subset: [1,3,4], Remaining set: {}, Current sum: 8

Why: Sum too big, backtrack

Step 22: Try subset with 3 and 4 excluded, only 1 included

Subset: [1], Remaining set: {}, Current sum: 1

Why: No solution found

Step 23: Try subset with 1 and 4 excluded, only 3 included

Subset: [3], Remaining set: {}, Current sum: 3

Why: No solution found

Step 24: Try subset with 1 and 3 excluded, only 4 included

Subset: [4], Remaining set: {}, Current sum: 4

Why: No solution found

Step 25: Try subset with 1 and 3 and 4 excluded, empty subset

Subset: [], Remaining set: {}, Current sum: 0

Why: No solution found

Result:

No subset sums exactly to 6

Annotated Code

DSA C++

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

bool backtrackSubsetSum(const vector<int>& set, int target, int index, int currentSum) {
    if (currentSum == target) return true; // found exact sum
    if (currentSum > target || index == set.size()) return false; // overshoot or no elements

    // include current element
    if (backtrackSubsetSum(set, target, index + 1, currentSum + set[index]))
        return true;

    // exclude current element
    if (backtrackSubsetSum(set, target, index + 1, currentSum))
        return true;

    return false;
}

int main() {
    vector<int> set = {1, 3, 4};
    int target = 6;
    bool result = backtrackSubsetSum(set, target, 0, 0);
    if (result) cout << "Subset with sum " << target << " exists\n";
    else cout << "No subset sums exactly to " << target << "\n";
    return 0;
}

if (currentSum == target) return true; // found exact sum

Check if current subset sum matches target

if (currentSum > target || index == set.size()) return false; // overshoot or no elements

Stop if sum too big or no more elements

if (backtrackSubsetSum(set, target, index + 1, currentSum + set[index])) return true;

Try including current element

if (backtrackSubsetSum(set, target, index + 1, currentSum)) return true;

Try excluding current element

Output

No subset sums exactly to 6

Complexity Analysis

Time: O(2^n) because each element can be included or excluded, creating a binary tree of choices

Space: O(n) due to recursion stack depth up to n elements

vs Alternative: Greedy tries one choice at a time and can fail; backtracking tries all combinations but is slower

Edge Cases

Empty set

Returns false unless target is zero

DSA C++

if (currentSum == target) return true;

Single element equal to target

Returns true immediately

DSA C++

if (currentSum == target) return true;

All elements larger than target

Returns false after pruning

DSA C++

if (currentSum > target || index == set.size()) return false;

When to Use This Pattern

When a problem requires trying all combinations to find a solution and greedy choices fail, use backtracking to explore all options systematically.

Common Mistakes

Mistake: Trying greedy approach for subset sum and assuming it always works
Fix: Use backtracking to try all subsets because greedy can miss valid combinations

Summary

Backtracking tries all possible choices step-by-step to find a solution.

Use backtracking when greedy choices can miss the correct answer.

The key is to explore all options and backtrack when a path fails.

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