Backtracking Concept and Decision Tree Visualization in DSA C++ - Practice Problems & Challenges

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 2 3 | 4 1 | 5 |

B 1 2 3 | 5 |

C 1 4 | 3 2 | 5 |

D 1 4 | 2 3 | 5 |

💡 Hint

Trace the recursion and note the order of elements and their sums.

The code finds all subsets of nums that sum to 5 without reusing elements. The subsets are printed in the order found: {1,4}, {2,3}, and {5}.

🧠 Conceptual

intermediate

Backtracking Decision Tree Nodes Count

If a backtracking algorithm explores all subsets of a set of size 4, how many nodes are there in the decision tree including the root?

A 31

B 15

C 16

D 8

💡 Hint

Each element can be either included or excluded, forming a binary tree.

For n elements, the decision tree has 2^n leaves and 2^n - 1 internal nodes, total nodes = 2^(n+1) - 1. For n=4, total nodes = 31.

🔧 Debug

advanced

Identify the Backtracking Logic Error

What error does the following backtracking code produce when trying to generate permutations of {1,2,3}? #include #include using namespace std; void backtrack(vector& nums, vector& used, vector& current) { if (current.size() == nums.size()) { for (int x : current) cout << x << " "; cout << "\n"; return; } for (int i = 0; i < nums.size(); i++) { if (!used[i]) { current.push_back(nums[i]); backtrack(nums, used, current); current.pop_back(); used[i] = false; } } } int main() { vector nums = {1, 2, 3}; vector used(3, false); vector current; backtrack(nums, used, current); return 0; }

A No output; infinite recursion

B Outputs repeated permutations with duplicates

C Outputs correct permutations

D Compilation error due to missing headers

💡 Hint

Check when 'used[i]' is set to true and false.

The code never sets used[i] to true before recursion, so the same element can be reused infinitely causing infinite recursion and no output.

❓ Predict Output

advanced

Output of N-Queens Backtracking

What is the output of the following code snippet that prints the number of solutions for 4-Queens problem using backtracking?

DSA C++

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

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

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

int main() {
    int n = 4;
    vector<int> queens(n, -1);
    int count = 0;
    solve(0, n, queens, count);
    cout << count << endl;
    return 0;
}

A 4

B 0

C 2

D 1

💡 Hint

Recall the known number of solutions for 4-Queens problem.

The 4-Queens problem has exactly 2 distinct solutions. The code counts all valid placements.

🧠 Conceptual

expert

Backtracking Pruning Effect on Decision Tree Size

How does pruning in backtracking affect the size of the decision tree compared to exploring all possibilities?

A Pruning increases the number of nodes because it adds extra checks at each node.

B Pruning reduces the number of nodes by cutting branches early, decreasing tree size exponentially in best cases.

C Pruning has no effect on the decision tree size; it only changes the order of traversal.

D Pruning converts the decision tree into a linked list, reducing complexity to linear.

💡 Hint

Think about how skipping impossible paths affects the search space.

Pruning stops exploring branches that cannot lead to a solution, thus reducing the number of nodes visited and effectively shrinking the decision tree size.

Practice

1. What is the main idea behind backtracking in algorithms?

easy

A. Sort data before processing

B. Try all possible options and undo choices when they lead to dead ends

C. Use loops to repeat actions

D. Store data in arrays for quick access

Solution

1. Step 1: Understand backtracking purpose

   Backtracking tries all options to find solutions by exploring choices step-by-step.

2. Step 2: Recognize undoing choices

   When a choice leads to no solution, backtracking reverses it to try others.

3. Final Answer:

   Try all possible options and undo choices when they lead to dead ends -> Option B

4. Quick Check:

   Backtracking = Try and undo choices [OK]

Hint: Backtracking means try, undo if fails, then try next [OK]

Common Mistakes:

• Confusing backtracking with sorting
• Thinking backtracking only uses loops
• Assuming backtracking stores all data upfront

2. Which of the following is the correct syntax to start a backtracking function in C++?

easy

A. backtrack() -> void { }

B. int backtrack[] = {0};

C. void backtrack(int step) { /* code */ }

D. function backtrack(int step) { }

Solution

1. Step 1: Identify valid C++ function syntax

   In C++, functions are declared with return type, name, and parameters inside parentheses.

2. Step 2: Check each option

   void backtrack(int step) { /* code */ } uses correct C++ syntax: return type void, function name, parameter list.

3. Final Answer:

   void backtrack(int step) { /* code */ } -> Option C

4. Quick Check:

   C++ function syntax = void backtrack(int step) { /* code */ } [OK]

Hint: C++ functions start with return type and parentheses [OK]

Common Mistakes:

• Using JavaScript or Python syntax in C++
• Missing return type in function declaration
• Using arrow notation which is invalid in C++

3. Consider this backtracking code snippet in C++ that prints all subsets of {1, 2}:

void backtrack(vector<int>& subset, int start) {
  if (start == 2) {
    for (int x : subset) cout << x << ' ';
    cout << '\n';
    return;
  }
  backtrack(subset, start + 1);
  subset.push_back(start + 1);
  backtrack(subset, start + 1);
  subset.pop_back();
}

int main() {
  vector<int> subset;
  backtrack(subset, 0);
  return 0;
}

What is the output?

medium

A. \n \n1 \n1 2 \n

B. \n\n\n\n\n\n\n

C. \n\n\n\n1 2 \n

D. \n\n\n2 \n1 \n1 2 \n

Solution

1. Step 1: Trace recursive calls without adding elements

   First call prints empty subset (no elements), so prints blank line.

2. Step 2: Trace recursive calls adding elements

   Then adds 1, prints '1 ', then adds 2, prints '1 2 ', and also prints '2 ' when only 2 is added.

3. Final Answer:

   \n \n1 \n1 2 \n -> Option A

4. Quick Check:

   All subsets printed = \n \n1 \n1 2 \n [OK]

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

Common Mistakes:

• Forgetting to pop elements after recursion
• Mixing order of adding elements
• Missing empty subset output

4. The following backtracking code tries to generate all binary strings of length 2 but has a bug:

void backtrack(string& s, int pos) {
  if (pos == 2) {
    cout << s << '\n';
    return;
  }
  s[pos] = '0';
  backtrack(s, pos + 1);
  s[pos] = '1';
  backtrack(s, pos + 1);
}

int main() {
  string s = "";
  backtrack(s, 0);
  return 0;
}

What is the bug?

medium

A. String s is empty and cannot assign characters by index

B. The base case condition is incorrect

C. The recursion does not increment position

D. The output statements are missing

Solution

1. Step 1: Check string initialization

   String s is empty (length 0), so s[pos] = '0' causes out-of-range error.

2. Step 2: Understand string indexing requirement

   To assign by index, string must have length at least 2, e.g., initialized as "00".

3. Final Answer:

   String s is empty and cannot assign characters by index -> Option A

4. Quick Check:

   Empty string indexing causes error [OK]

Hint: Initialize string length before assigning by index [OK]

Common Mistakes:

• Ignoring string length before assignment
• Thinking base case is wrong
• Missing recursion increment

5. You want to use backtracking to solve the N-Queens problem for N=4. Which of these best describes the decision tree visualization for this problem?

hard

A. The tree has only one branch because queens are placed sequentially without choices

B. Each node stores the entire chessboard state and branches by swapping queens

C. Each level represents removing queens from the board to find solutions

D. Each level represents placing a queen in a row, branching by possible columns without conflicts

Solution

1. Step 1: Understand N-Queens backtracking

   Backtracking places queens row by row, choosing columns that don't conflict.

2. Step 2: Visualize decision tree levels

   Each level corresponds to a row; branches represent valid column choices for that row.

3. Final Answer:

   Each level represents placing a queen in a row, branching by possible columns without conflicts -> Option D

4. Quick Check:

   Decision tree levels = rows, branches = columns [OK]

Hint: Decision tree levels = rows, branches = valid columns [OK]

Common Mistakes:

• Thinking tree branches represent swapping queens
• Assuming only one branch per level
• Confusing placing with removing queens