Why Backtracking and What Greedy Cannot Solve in DSA C++ - See It Work

Why Backtracking and What Greedy Cannot Solve

📖 Scenario: Imagine you are organizing a treasure hunt game. You have a list of clues and paths to follow. Some paths lead to dead ends, and some lead to the treasure. You want to find the correct path to the treasure.Sometimes, choosing the best immediate step (greedy choice) does not lead to the treasure. You need to try different paths and backtrack if you hit a dead end.

🎯 Goal: Build a simple program that tries all possible paths to find the treasure using backtracking. Understand why greedy approach fails in this case.

📋 What You'll Learn

Create a list of paths with their next possible steps

Use a variable to track the current path

Implement backtracking to explore all paths

Print the successful path to the treasure

💡 Why This Matters

🌍 Real World

Backtracking is used in puzzles, games, and decision-making problems where all possibilities must be explored.

💼 Career

Understanding backtracking helps in solving complex problems like scheduling, routing, and constraint satisfaction in software development.

1

Create the paths data structure

Create a std::map> called paths with these exact entries: 'A': {'B', 'C'}, 'B': {'D'}, 'C': {'D', 'E'}, 'D': {'F'}, 'E': {}, 'F': {}

DSA C++

// Your code here

Hint

Use std::map> to store paths from one point to next possible points.

2

Create a variable to track the current path

Create a std::vector called current_path and initialize it with 'A' as the starting point

DSA C++

#include 
#include 
#include 

std::map> paths = {
    {'A', {'B', 'C'}},
    {'B', {'D'}},
    {'C', {'D', 'E'}},
    {'D', {'F'}},
    {'E', {}},
    {'F', {}}
};

// Your code here

Hint

Use std::vector to keep track of the path you are currently exploring.

3

Implement backtracking function

Write a recursive function bool backtrack(char node) that tries all next steps from paths[node]. Add the next node to current_path, call backtrack recursively, and remove the node if it does not lead to 'F'. Return true if 'F' is found.

DSA C++

#include 
#include 
#include 

std::map> paths = {
    {'A', {'B', 'C'}},
    {'B', {'D'}},
    {'C', {'D', 'E'}},
    {'D', {'F'}},
    {'E', {}},
    {'F', {}}
};

std::vector current_path = {'A'};

// Write backtrack function here
// Your code here

Hint

Use recursion to try each next node. Add it to current_path, recurse, and remove it if no success.

4

Print the successful path

Call backtrack('A') and then print the current_path as a sequence of characters separated by -> and ending with -> null

DSA C++

#include 
#include 
#include 

std::map> paths = {
    {'A', {'B', 'C'}},
    {'B', {'D'}},
    {'C', {'D', 'E'}},
    {'D', {'F'}},
    {'E', {}},
    {'F', {}}
};

std::vector current_path = {'A'};

bool backtrack(char node) {
    if (node == 'F') {
        return true;
    }
    for (char next_node : paths[node]) {
        current_path.push_back(next_node);
        if (backtrack(next_node)) {
            return true;
        }
        current_path.pop_back();
    }
    return false;
}

// Call backtrack and print the path
// Your code here

Hint

Call backtrack('A') and print each character in current_path separated by ->, ending with -> null.

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