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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Backtracking Path Exploration

What is the printed output of the following Go code that uses backtracking to find all subsets of {1, 2}?

DSA Go

package main
import "fmt"
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{})
}

A

[]
[2]
[1]
[1 2]

B

[]
[1]
[1 2]
[2]

C

[1]
[1 2]
[2]

D

[1 2]
[1]
[2]
[]

💡 Hint

Trace the recursive calls and note when the path is printed.

The function prints the current path before exploring further elements. It starts with an empty path, then adds 1, then adds 2, then backtracks to add 2 alone.

🧠 Conceptual

intermediate

Backtracking Decision Tree Nodes Count

How many nodes are there in the decision tree when backtracking to generate all permutations of 3 distinct elements?

A 24

B 15

C 6

D 16

💡 Hint

Count all partial and complete permutations including the root node.

For 3 elements, the decision tree has 1 (root) + 3 + 6 + 6 = 16 nodes representing all partial and full permutations.

🔧 Debug

advanced

Identify the Backtracking Logic Error

What error does the following Go backtracking code produce when trying to generate combinations of size 2 from {1,2,3}?

DSA Go

package main
import "fmt"
func backtrack(nums []int, start int, path []int, k int) {
    if len(path) == k {
        fmt.Println(path)
        return
    }
    for i := start; i < len(nums); i++ {
        backtrack(nums, i+1, append(path, nums[i]), k)
    }
}
func main() {
    backtrack([]int{1,2,3}, 0, []int{}, 2)
}

A runtime error: index out of range

B prints all combinations correctly

C compilation error: missing return statement

D infinite recursion

💡 Hint

Check the loop boundary condition and array indexing.

The loop uses i <= len(nums), which causes an index out of range error when i equals len(nums).

🚀 Application

advanced

Backtracking to Solve N-Queens: Number of Solutions

Using backtracking, how many distinct solutions exist for the 4-Queens problem?

A 8

B 4

C 2

D 16

💡 Hint

Recall the classic known count of 4-Queens solutions.

The 4-Queens problem has exactly 2 distinct solutions found by backtracking.

❓ Predict Output

expert

Backtracking with Pruning: Output of Partial Paths

What is the output of this Go code that uses backtracking with pruning to generate subsets of {1,2,3} where the sum is less than 4?

DSA Go

package main
import "fmt"
func backtrack(nums []int, start int, path []int, sum int) {
    if sum >= 4 {
        return
    }
    fmt.Println(path)
    for i := start; i < len(nums); i++ {
        backtrack(nums, i+1, append(path, nums[i]), sum+nums[i])
    }
}
func main() {
    backtrack([]int{1,2,3}, 0, []int{}, 0)
}

A

[]
[1]
[1 2]
[2]
[3]

B

[]
[1]
[1 2]
[1 3]
[2]
[2 3]
[3]

C

[]
[1]
[1 2]
[1 3]
[2]
[3]

D

[]
[1]
[1 2]
[2]
[2 3]
[3]

💡 Hint

Trace sums and note when pruning stops recursion.

The pruning check occurs before printing, so paths with sum >=4 like [1 3] (sum=4), [2 3] (5), [1 2 3] (6) are pruned without printing.

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