Why Backtracking and What Greedy Cannot Solve in DSA C++ - Test Your Knowledge

Practice - 5 Tasks

1fill in blank

easy

Complete the code to start the backtracking recursion from the first element.

DSA C++

void backtrack(int index) {
    if (index == n) {
        // process solution
        return;
    }
    // try options
}

int main() {
    int n = 5;
    backtrack([1]);
    return 0;
}

Drag options to blanks, or click blank then click option'

An

B1

C0

D-1

Attempts:

3 left

💡 Hint

Common Mistakes

Starting from index 1 skips the first element.

Starting from n means no elements to process.

Starting from -1 is invalid index.

Backtracking usually starts from index 0 to explore all options from the beginning.

2fill in blank

medium

Complete the code to check if the current partial solution is valid before continuing.

DSA C++

bool isValid(vector<int>& solution) {
    // check constraints
    return solution.size() <= [1];
}

Drag options to blanks, or click blank then click option'

A0

Bn

Csolution.size()

DINT_MAX

Attempts:

3 left

💡 Hint

Common Mistakes

Using 0 always returns false except empty solution.

Using solution.size() compares size to itself, always true.

Using INT_MAX is too large and not meaningful here.

We check if the solution size does not exceed the problem size n.

3fill in blank

hard

Fix the error in the backtracking recursive call to explore next options.

DSA C++

void backtrack(int index) {
    if (index == n) {
        // process solution
        return;
    }
    for (int choice = 0; choice < options.size(); ++choice) {
        solution.push_back(options[choice]);
        backtrack([1]);
        solution.pop_back();
    }
}

Drag options to blanks, or click blank then click option'

Aindex + 1

Bindex

Cchoice

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using index again causes infinite recursion.

Using choice as index is incorrect because choice is option index.

Using 0 restarts recursion endlessly.

We must move to the next index to avoid infinite recursion and explore next positions.

4fill in blank

hard

Fill both blanks to create a condition where greedy fails but backtracking succeeds.

DSA C++

vector<int> nums = {2, 4, 6, 10};
int target = 16;

bool canSum(int sum, int index) {
    if (sum == target) return true;
    if (sum > target || index == [1]) return false;
    return canSum(sum + nums[index], index + 1) || canSum(sum, [2]);
}

Drag options to blanks, or click blank then click option'

Anums.size()

B0

Cindex + 1

Dtarget

Attempts:

3 left

💡 Hint

Common Mistakes

Using 0 as index stop condition causes infinite recursion.

Using target as index is invalid.

Not increasing index in recursive calls causes infinite loops.

We stop when index reaches nums.size(), and explore skipping current index by calling canSum with index + 1.

5fill in blank

hard

Fill all three blanks to implement a backtracking solution that finds all subsets summing to target, showing why greedy fails.

DSA C++

void findSubsets(int index, int currentSum) {
    if (currentSum == target) {
        results.push_back(currentSubset);
        return;
    }
    if (index == [1] || currentSum > target) return;
    // include nums[index]
    currentSubset.push_back(nums[[2]]);
    findSubsets(index + 1, currentSum + nums[[3]]);
    currentSubset.pop_back();
    // exclude nums[index]
    findSubsets(index + 1, currentSum);
}

Drag options to blanks, or click blank then click option'

Anums.size()

Bindex

Dtarget

Attempts:

3 left

💡 Hint

Common Mistakes

Using target as index limit causes errors.

Using wrong index to access nums causes out-of-range errors.

Not increasing index causes infinite recursion.

Stop when index reaches nums.size(), include nums[index] by accessing nums[index], and recurse with index + 1 to explore all subsets.

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