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

Challenge - 5 Problems

🧠 Conceptual

easy

What is Backtracking?

Which statement best describes the backtracking strategy?

A Try all possibilities greedily, always picking the highest value option

B Memoize all recursive calls to avoid recomputation

C Divide the problem into independent subproblems and combine their solutions

D Build a solution incrementally, abandoning a path as soon as it violates constraints and trying the next option

💡 Hint

Think about what happens when a partial solution fails a constraint — do we keep going or turn back?

Backtracking builds solutions step-by-step. At each step, if the current partial solution violates a constraint, we undo the last choice (backtrack) and try the next available option. This is different from greedy (always picks best local option), divide-and-conquer (independent subproblems), and DP (memoization).

❓ Predict Output

intermediate

Trace a Simple Backtracking Function

What does this C# backtracking function print for n=2?

DSA C#

void Solve(int n, List<int> path) {
    if (path.Count == n) {
        Console.WriteLine("[" + string.Join(",", path) + "]");
        return;
    }
    for (int i = 1; i <= n; i++) {
        if (!path.Contains(i)) {
            path.Add(i);
            Solve(n, path);
            path.RemoveAt(path.Count - 1);  // backtrack
        }
    }
}
Solve(2, new List<int>());

A

[1,2]
[2,1]

B [1,2]

C

[1,1]
[2,2]

D

[1,2]
[1,2]

💡 Hint

Trace what path contains at each recursive call. The backtrack line removes the last added element.

n=2: path starts empty. Add 1→path=[1]. Add 2→path=[1,2]→print [1,2]. Backtrack→path=[1]. No more options (2 used). Backtrack→path=[]. Add 2→path=[2]. Add 1→path=[2,1]→print [2,1]. Backtrack. Done. Output: [1,2] then [2,1].

🧠 Conceptual

intermediate

Decision Tree Depth

In a backtracking decision tree for generating all permutations of n elements, what is the maximum depth of the tree?

A n

B 2^n

C n²

D n!

💡 Hint

Each level of the tree corresponds to choosing one element for the current position in the permutation.

The decision tree has depth n because we make exactly n choices — one element per position in the permutation. At depth 1 we choose the first element, at depth 2 the second, and so on until depth n where the permutation is complete. The number of leaves is n! (total permutations), but the depth is just n.

🔧 Debug

intermediate

Find the Missing Backtrack Step

This code is supposed to find all subsets but produces duplicates. What is missing?

DSA C#

void Subsets(int[] nums, int start, List<int> current, List<List<int>> result) {
    result.Add(new List<int>(current));
    for (int i = start; i < nums.Length; i++) {
        current.Add(nums[i]);
        Subsets(nums, i + 1, current, result);
        // BUG: missing something here
    }
}

A current.Clear() should be added after the recursive call

B start should be reset to 0 after each call

C current.RemoveAt(current.Count - 1) should be added after the recursive call to backtrack

D result.Add should be inside the loop, not before it

💡 Hint

After exploring all subsets that include nums[i], we must undo adding nums[i] before trying nums[i+1].

After the recursive call returns, nums[i] is still in current — it was never removed. The next iteration adds nums[i+1] on top of a list that still contains nums[i], causing duplicates and wrong subsets. The fix is current.RemoveAt(current.Count - 1) after the recursive call — this is the backtrack step that undoes the choice.

🚀 Application

hard

Pruning in Backtracking

In a backtracking solution for N-Queens, which condition correctly prunes invalid placements before recursing?

DSA C#

bool IsSafe(int[] board, int row, int col) {
    for (int i = 0; i < row; i++) {
        if (/* condition */) return false;
    }
    return true;
}

A board[i] == row

B board[i] == col || board[i] - i == col - row || board[i] + i == col + row

C board[i] > col

D i == row

💡 Hint

A queen at row i, column board[i] attacks the current (row, col) if they share a column or either diagonal.

Three attack conditions: (1) same column: board[i]==col. (2) same major diagonal (top-left to bottom-right): column difference equals row difference → board[i]-i == col-row. (3) same minor diagonal: board[i]+i == col+row. If any condition holds, placement is unsafe and we prune this branch without recursing.

Practice

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

easy

A. Use loops to repeat actions

B. Sort data before processing

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

D. Store data in a queue for processing

Solution

1. Step 1: Understand backtracking purpose

   Backtracking tries all options step-by-step and goes back if a choice fails.

2. Step 2: Compare with other options

   Sorting, looping, and queues are different concepts not related to undoing choices.

3. Final Answer:

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

4. Quick Check:

   Backtracking = Undo and try options [OK]

Hint: Backtracking means try and undo choices to find solutions [OK]

Common Mistakes:

• Confusing backtracking with sorting or looping
• Thinking backtracking only uses loops
• Ignoring the undo step in backtracking

2. Which of the following is the correct C# syntax to start a backtracking recursive function named Backtrack with an integer parameter step?

easy

A. def Backtrack(step): ...

B. void Backtrack(int step) { ... }

C. Backtrack(int step) => { ... }

D. function Backtrack(step) { ... }

Solution

1. Step 1: Identify C# function syntax

   C# uses return type before function name and parameters in parentheses.

2. Step 2: Check options

   void Backtrack(int step) { ... } matches C# syntax. function Backtrack(step) { ... } is JavaScript style, C is invalid C# syntax, A is Python.

3. Final Answer:

   void Backtrack(int step) { ... } -> Option B

4. Quick Check:

   C# method syntax = void Name(params) [OK]

Hint: C# methods start with return type and parentheses [OK]

Common Mistakes:

• Using JavaScript or Python syntax in C#
• Omitting return type in method declaration
• Using arrow syntax incorrectly in C#

3. Consider the following C# backtracking code snippet:

void Backtrack(int step, int max) {
  if (step == max) {
    Console.WriteLine(step);
    return;
  }
  if (step > max) {
    return;
  }
  Backtrack(step + 1, max);
  Backtrack(step + 2, max);
}

Backtrack(0, 3);

What will be the printed output?

medium

A. 0
1
2
3

B. 3
4

C. 2
3

D. 3
3
3

Solution

1. Step 1: Trace recursive calls

   Starting at step=0, max=3. Calls increase step by 1 or 2 until step==3.

2. Step 2: Identify base cases printed

   Paths reaching step==3 print 3. Three paths reach 3: 0->1->2->3, 0->1->3, and 0->2->3.

3. Final Answer:

   3 3 3 -> Option D

4. Quick Check:

   Base case prints 3 three times [OK]

Hint: Follow each recursive path to base case print [OK]

Common Mistakes:

• Counting intermediate steps as output
• Missing one of the recursive paths
• Confusing step values printed

4. The following C# backtracking code is intended to print all subsets of {1, 2}, but it has an error:

void Subsets(int index, List<int> current) {
  if (index == 2) {
    Console.WriteLine(string.Join(",", current));
    return;
  }
  Subsets(index + 1, current);
  current.Add(index + 1);
  Subsets(index + 1, current);
}

What is the main problem?

medium

A. The list current is not restored after adding elements, causing incorrect subsets

B. The base case condition is wrong

C. The function should return a value

D. The index variable is not incremented

Solution

1. Step 1: Analyze list modification

   After adding element to current, it is not removed before backtracking, so subsets accumulate extra elements.

2. Step 2: Identify fix

   Need to remove last added element after recursive call to restore state.

3. Final Answer:

   The list current is not restored after adding elements, causing incorrect subsets -> Option A

4. Quick Check:

   Backtracking requires undoing changes [OK]

Hint: Always undo list changes after recursive calls [OK]

Common Mistakes:

• Forgetting to remove added elements after recursion
• Misunderstanding base case
• Expecting return value from void method

5. You want to use backtracking to find all ways to climb a staircase of 4 steps, taking either 1 or 2 steps at a time. Which decision tree correctly represents the choices at each step?

medium

A. Root at step 0, branches to step 1 and step 2, each branch continues similarly until step 4

B. Root at step 4, branches to step 3 and step 2, moving backward

C. Root at step 0, branches only to step 1 repeatedly until step 4

D. Root at step 1, branches to step 3 and step 4 directly

Solution

1. Step 1: Understand problem steps

   Starting at step 0, choices are to move 1 or 2 steps forward until reaching step 4.

2. Step 2: Match decision tree structure

   Root at step 0, branches to step 1 and step 2, each branch continues similarly until step 4 shows root at 0 with branches to 1 and 2, continuing until 4, matching the problem.

3. Final Answer:

   Root at step 0, branches to step 1 and step 2, each branch continues similarly until step 4 -> Option A

4. Quick Check:

   Decision tree = choices from start to goal [OK]

Hint: Decision tree starts at initial state, branches by choices [OK]

Common Mistakes:

• Starting decision tree at goal instead of start
• Ignoring possible step sizes
• Skipping intermediate steps in tree