Backtracking Concept and Decision Tree Visualization in DSA Go - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to start backtracking from the first position.

DSA Go

func backtrack(pos int) {
    if pos == len(nums) {
        fmt.Println(path)
        return
    }
    for i := 0; i < len(nums); i++ {
        if used[i] {
            continue
        }
        used[i] = true
        path = append(path, nums[i])
        backtrack([1])
        path = path[:len(path)-1]
        used[i] = false
    }
}

Drag options to blanks, or click blank then click option'

A0

Bpos

Ci

Dpos+1

Attempts:

3 left

💡 Hint

Common Mistakes

Using pos instead of pos+1 causes infinite recursion.

Using i as position confuses index with recursion depth.

We move to the next position by increasing pos by 1 to explore further choices.

2fill in blank

medium

Complete the code to mark the element as unused after backtracking.

DSA Go

used[i] = true
path = append(path, nums[i])
backtrack(pos + 1)
path = path[:len(path)-1]
[1]

Drag options to blanks, or click blank then click option'

Aused[i] = true

Bpath = append(path, nums[i])

Cused[i] = false

Dpos = pos - 1

Attempts:

3 left

💡 Hint

Common Mistakes

Forgetting to mark used[i] false causes missing permutations.

Marking used[i] true again causes no progress.

After exploring with nums[i], we mark it unused to allow other branches to use it.

3fill in blank

hard

Fix the error in the base case condition to stop recursion correctly.

DSA Go

if [1] == len(nums) {
    fmt.Println(path)
    return
}

Drag options to blanks, or click blank then click option'

Ai

Bpos

Clen(path)

Dused

Attempts:

3 left

💡 Hint

Common Mistakes

Using i instead of pos causes wrong stopping condition.

Using len(path) can work but is less clear than pos.

The recursion depth is tracked by pos, so we stop when pos reaches length of nums.

4fill in blank

hard

Fill both blanks to create a decision tree node with current path and explore next level.

DSA Go

node := TreeNode{
    value: [1],
    children: []TreeNode{},
}
for i := 0; i < len(nums); i++ {
    if !used[i] {
        used[i] = true
        path = append(path, nums[i])
        node.children = append(node.children, [2])
        path = path[:len(path)-1]
        used[i] = false
    }
}

Drag options to blanks, or click blank then click option'

Aappend([]int{}, path...)

Bbacktrack(pos + 1)

Cbacktrack(pos)

Dpath

Attempts:

3 left

💡 Hint

Common Mistakes

Using path directly causes all nodes to share same slice.

Calling backtrack with pos causes infinite loops.

We copy current path for node value and recursively build children by calling backtrack with next position.

5fill in blank

hard

Fill all three blanks to build a map of paths with their lengths filtered by length > 2.

DSA Go

result := map[string]int{
    [1]: [2],
}
filtered := map[string]int{}
for k, v := range result {
    if v [3] 2 {
        filtered[k] = v
    }
}

Drag options to blanks, or click blank then click option'

A"path"

Blen(path)

C>

D"length"

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong key names causes map errors.

Using wrong comparison operator filters incorrectly.

We use "path" as key, length of path as value, and filter where length is greater than 2.

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