Backtracking Concept and Decision Tree Visualization in DSA Go

Mental Model

Backtracking tries all choices step-by-step and goes back when a choice doesn't work.

Analogy: Imagine walking in a maze and choosing paths. If you hit a dead end, you return to the last fork and try a different path.

Start
  ↓
Choice 1 -> Dead End
  ↓
Backtrack ← Choice 2 -> Success
  ↓
End

Dry Run Walkthrough

Input: Find all subsets of [1, 2] using backtracking

Goal: List all possible subsets by choosing or skipping each number

Step 1: Start with empty subset []

[] ↑

Why: We begin with no elements chosen

Step 2: Choose 1, subset becomes [1]

[1] ↑

Why: Try including first element

Step 3: Choose 2, subset becomes [1, 2]

[1, 2] ↑

Why: Try including second element after first

Step 4: Backtrack: remove 2, subset back to [1]

[1] ↑

Why: Try skipping second element after first

Step 5: Backtrack: remove 1, subset back to []

[] ↑

Why: Try skipping first element

Step 6: Choose 2, subset becomes [2]

[2] ↑

Why: Try including second element without first

Step 7: Backtrack: remove 2, subset back to []

[] ↑

Why: Try skipping second element as well

Result:

[] -> [1] -> [1, 2] -> [1] -> [] -> [2] -> []
All subsets found

Annotated Code

DSA Go

package main

import "fmt"

func backtrack(nums []int, start int, path []int, res *[][]int) {
    // Add current subset to results
    temp := make([]int, len(path))
    copy(temp, path)
    *res = append(*res, temp)

    // Explore further elements
    for i := start; i < len(nums); i++ {
        // Choose nums[i]
        path = append(path, nums[i])
        backtrack(nums, i+1, path, res) // Recurse
        // Backtrack: remove last element
        path = path[:len(path)-1]
    }
}

func main() {
    nums := []int{1, 2}
    res := [][]int{}
    backtrack(nums, 0, []int{}, &res)
    for _, subset := range res {
        fmt.Println(subset)
    }
}

temp := make([]int, len(path)) copy(temp, path) *res = append(*res, temp)

Save current subset to results to keep track of all choices

for i := start; i < len(nums); i++ {

Loop through remaining elements to explore choices

path = append(path, nums[i])

Choose current element to add to subset

backtrack(nums, i+1, path, res)

Recurse to explore further choices after current

path = path[:len(path)-1]

Backtrack by removing last chosen element to try other options

Output

[]

[1]

[1 2]

[2]

Complexity Analysis

Time: O(2^n) because each element can be chosen or skipped, creating all subsets

Space: O(n) for recursion stack and temporary path storage

vs Alternative: Backtracking is more efficient than generating all subsets blindly because it builds subsets step-by-step and stops early if needed

Edge Cases

empty input list

returns only the empty subset []

DSA Go

for i := start; i < len(nums); i++ {

single element list

returns [] and [element]

DSA Go

for i := start; i < len(nums); i++ {

When to Use This Pattern

When you need to explore all possible combinations or subsets and undo choices to try others, use backtracking because it systematically tries all options.

Common Mistakes

Mistake: Not removing the last element after recursion, causing incorrect subsets
Fix: Always backtrack by removing the last chosen element after recursive call

Mistake: Appending the path slice directly without copying, leading to all results being the same
Fix: Copy the current path slice before appending to results

Summary

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

Use it when you want to find all combinations, subsets, or permutations.

The key is to choose, explore, then undo the choice to try others.

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 a queue for processing

Solution

1. Step 1: Understand backtracking approach

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

2. Step 2: Compare with other options

   Sorting, loops, 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 B

4. Quick Check:

   Backtracking = Try and undo choices [OK]

Hint: Backtracking means try, fail, undo, and try again [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 way to start a backtracking function in Go?

easy

A. func backtrack(path []int, choices []int) { }

B. func backtrack(path int, choices int) { }

C. func backtrack() int { return 0 }

D. func backtrack(choices []string) string { return "" }

Solution

1. Step 1: Check parameter types for backtracking

   Backtracking usually passes current path (slice of ints) and available choices (slice of ints).

2. Step 2: Validate function signature

   func backtrack(path []int, choices []int) { } matches expected signature with slices for path and choices.

3. Final Answer:

   func backtrack(path []int, choices []int) { } -> Option A

4. Quick Check:

   Backtracking uses slices for path and choices [OK]

Hint: Backtracking functions usually take slices for path and choices [OK]

Common Mistakes:

• Using single int instead of slices for path and choices
• Returning values when not needed
• Using wrong data types like string instead of int

3. What will be the output of this Go code snippet that uses backtracking to generate subsets?

func backtrack(nums []int, start int, path []int) {
    fmt.Println(path)
    for i := start; i < len(nums); i++ {
        backtrack(nums, i+1, append(path, nums[i]))
    }
}

func main() {
    backtrack([]int{1, 2}, 0, []int{})
}

medium

A. []
[2]
[1]
[1 2]

B. [1]
[2]
[1 2]

C. [1 2]
[2]
[1]

D. []
[1]
[1 2]
[2]

Solution

1. Step 1: Trace initial call and print

   First call prints empty path: []

2. Step 2: Trace recursive calls

   From start=0, i=0: append 1 -> print [1], then recurse with i=1: append 2 -> print [1 2]

3. Step 3: Trace next iteration

   From start=0, i=1: append 2 -> print [2]

4. Final Answer:

   [] [1] [1 2] [2] -> Option D

5. Quick Check:

   Subsets printed in order with empty first [OK]

Hint: Backtracking prints empty path first, then builds subsets [OK]

Common Mistakes:

• Ignoring empty subset output
• Mixing order of subsets printed
• Not appending correctly in recursive calls

4. Identify the error in this backtracking code snippet in Go:

func backtrack(nums []int, start int, path []int) {
    if start == len(nums) {
        fmt.Println(path)
        return
    }
    backtrack(nums, start+1, path)
    backtrack(nums, start+1, append(path, nums[start]))
}

func main() {
    backtrack([]int{1, 2}, 0, []int{})
}

medium

A. Appending to path modifies original slice causing wrong output

B. Missing base case to stop recursion

C. No error; code correctly prints all subsets

D. Incorrect increment of start variable

Solution

1. Step 1: Check base case correctness

   Base case triggers when start equals length, printing current path.

2. Step 2: Check recursive calls

   Two calls: one excludes current element, one includes it by appending.

3. Step 3: Confirm no slice mutation issues

   append creates new slice, so original path is safe.

4. Final Answer:

   No error; code correctly prints all subsets -> Option C

5. Quick Check:

   Code prints all subsets correctly [OK]

Hint: Appending returns new slice; original path stays unchanged [OK]

Common Mistakes:

• Thinking append modifies original slice in place
• Missing base case causing infinite recursion
• Incorrect start increment causing wrong subsets

5. Given a decision tree for solving the N-Queens problem using backtracking, which of the following best describes the pruning step in the decision tree?

hard

A. Stopping exploration of branches where queens attack each other

B. Trying all possible queen placements without checks

C. Adding queens to all rows regardless of conflicts

D. Restarting the entire search after each queen placement

Solution

1. Step 1: Understand pruning in backtracking

   Pruning means cutting off branches that cannot lead to a solution early.

2. Step 2: Apply to N-Queens problem

   Branches where queens attack each other are invalid and should be stopped.

3. Final Answer:

   Stopping exploration of branches where queens attack each other -> Option A

4. Quick Check:

   Pruning = stop invalid branches early [OK]

Hint: Prune by stopping invalid queen placements early [OK]

Common Mistakes:

• Trying all placements without pruning
• Ignoring conflicts between queens
• Restarting search unnecessarily