Backtracking Concept and Decision Tree Visualization in DSA C#

Mental Model

Backtracking tries choices one by one and goes back if a choice does not work.

Analogy: Imagine walking in a maze: you pick a path, if it leads to a dead end, you return to the last fork and try a different path.

Start
  ↓
Choice 1 -> Dead End
  ↑
Choice 2 -> Continue -> Goal

Dry Run Walkthrough

Input: Find all ways to pick numbers from [1, 2] to make sum 3

Goal: List all sequences of numbers from [1, 2] that add up to 3 using backtracking

Step 1: Pick 1 first, current sum = 1

[1] sum=1

Why: Start with first choice to explore possible solutions

Step 2: Pick 1 again, current sum = 2

[1, 1] sum=2

Why: Try adding 1 again to reach the target sum

Step 3: Pick 1 again, current sum = 3 (target reached)

[1, 1, 1] sum=3

Why: Found a valid sequence that sums to 3

Step 4: Backtrack: remove last 1, sum back to 2

[1, 1] sum=2

Why: Try other choices after reaching target or dead end

Step 5: Pick 2 instead of 1, current sum = 4 (too big)

[1, 1, 2] sum=4

Why: Sum exceeded target, need to backtrack

Step 6: Backtrack twice to [1], sum=1

[1] sum=1

Why: Try different choices at earlier step

Step 7: Pick 2, current sum = 3 (target reached)

[1, 2] sum=3

Why: Found another valid sequence

Step 8: Backtrack to empty, sum=0

[] sum=0

Why: Try starting with different first choice

Step 9: Pick 2, current sum = 2

[2] sum=2

Why: Start with second choice

Step 10: Pick 1, current sum = 3 (target reached)

[2, 1] sum=3

Why: Found valid sequence

Step 11: Backtrack to [2], sum=2

[2] sum=2

Why: Try other choices after reaching target

Step 12: Pick 2, current sum = 4 (too big)

[2, 2] sum=4

Why: Sum exceeded target, backtrack

Step 13: Backtrack to empty, sum=0

[] sum=0

Why: All choices tried

Result:

Valid sequences: [1,1,1], [1,2], [2,1]

Annotated Code

DSA C#

using System;
using System.Collections.Generic;

class Backtracking {
    static void FindSequences(List<int> nums, int target, List<int> current, int currentSum, List<List<int>> results) {
        if (currentSum == target) {
            results.Add(new List<int>(current));
            return;
        }
        if (currentSum > target) {
            return;
        }
        foreach (int num in nums) {
            current.Add(num); // add choice
            FindSequences(nums, target, current, currentSum + num, results); // explore
            current.RemoveAt(current.Count - 1); // backtrack
        }
    }

    static void Main() {
        List<int> nums = new List<int> {1, 2};
        int target = 3;
        List<List<int>> results = new List<List<int>>();
        FindSequences(nums, target, new List<int>(), 0, results);
        foreach (var seq in results) {
            Console.WriteLine(string.Join(",", seq));
        }
    }
}

if (currentSum == target) {

Check if current sequence sums to target, then save it

if (currentSum > target) {

Stop exploring if sum exceeds target

current.Add(num);

Add a number choice to current sequence

FindSequences(nums, target, current, currentSum + num, results);

Recursively explore further choices

current.RemoveAt(current.Count - 1);

Remove last choice to backtrack and try others

Output

1,1,1

1,2

2,1

Complexity Analysis

Time: O(k^n) because at each step we try k choices and depth can be up to n (target sum)

Space: O(n) for recursion stack and current sequence storage

vs Alternative: Backtracking avoids exploring all sequences blindly by stopping early when sum exceeds target, unlike brute force which tries all sequences

Edge Cases

Empty nums list

No sequences found, function returns immediately

DSA C#

foreach (int num in nums) {

Target sum zero

Empty sequence is a valid solution

DSA C#

if (currentSum == target) {

No combination sums to target

No sequences added to results, output empty

DSA C#

if (currentSum > target) {

When to Use This Pattern

When a problem asks to find all combinations or sequences that satisfy a condition and you can try choices step-by-step, use backtracking to explore and undo choices efficiently.

Common Mistakes

Mistake: Not removing the last choice after recursive call, causing incorrect sequences
Fix: Always remove last added choice after recursion to backtrack

Mistake: Not stopping recursion when sum exceeds target, leading to unnecessary work
Fix: Add condition to return early if current sum is greater than target

Summary

Backtracking tries all possible choices step-by-step and goes back when a choice fails.

Use it when you need to explore all valid combinations or sequences under constraints.

The key is to add a choice, explore deeper, then remove it to try others.

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