Why Backtracking and What Greedy Cannot Solve in DSA Go - Why This Pattern

Mental Model

Backtracking tries all possible choices step-by-step to find the best solution, while greedy picks the best choice at each step without looking ahead.

Analogy: Imagine choosing toppings for a pizza: greedy picks the tastiest topping first and stops, but backtracking tries all topping combinations to find the yummiest pizza.

Start: Choices -> [Greedy picks 5+4=9>7 fail] -> Fail
Backtracking: Choices -> [Try 5] -> fail, backtrack -> [Try 4+3=7] -> Success

Dry Run Walkthrough

Input: Set of numbers: [5, 4, 3], target sum: 7

Goal: Find if any combination of numbers sums exactly to 7

Step 1: Greedy picks largest number 5 first

Chosen: 5, Remaining: [4,3]

Why: Greedy tries biggest number to reach target fast

Step 2: Greedy adds next largest 4, sum is 9 which is over target

Chosen: 5 -> 4, sum=9 > 7

Why: Greedy does not reconsider; it fails here

Step 3: Backtracking tries 5 first

Chosen: 5, Remaining: [4,3]

Why: Backtracking explores all options

Step 4: Backtracking adds 4, sum is 9 >7, backtrack

Chosen: 5 (backtrack from adding 4)

Why: Sum too big, undo

Step 5: Backtracking adds 3 to 5, sum=8 >7, backtrack

Chosen: 5 (backtrack from adding 3)

Why: Sum too big, no more choices from 5

Step 6: Backtracking removes 5, tries 4 next

Chosen: 4, Remaining: [3]

Why: Try different combination

Step 7: Backtracking adds 3, sum=7 exactly target

Chosen: 4 -> 3, sum=7

Why: Success! Found the combination

Result:

Found a combination that sums to 7 (4 + 3)

Annotated Code

DSA Go

package main

import "fmt"

func backtrack(nums []int, target int, start int, currentSum int) bool {
	if currentSum == target {
		return true
	}
	if currentSum > target {
		return false
	}
	for i := start; i < len(nums); i++ {
		// try including nums[i]
		if backtrack(nums, target, i+1, currentSum+nums[i]) {
			return true
		}
	}
	return false
}

func main() {
	nums := []int{5, 4, 3}
	target := 7
	if backtrack(nums, target, 0, 0) {
		fmt.Println("Found a combination that sums to", target)
	} else {
		fmt.Println("No combination sums exactly to", target)
	}
}

if currentSum == target { return true }

Check if current sum matches target to stop search

if currentSum > target { return false }

Stop exploring if sum exceeds target

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

Try each number starting from current index

if backtrack(nums, target, i+1, currentSum+nums[i]) { return true }

Recursively try including current number and check success

Output

Found a combination that sums to 7

Complexity Analysis

Time: O(2^n) because backtracking tries all subsets of n numbers

Space: O(n) for recursion stack in worst case

vs Alternative: Greedy runs in O(n) but can fail to find correct solution when local choices are misleading

Edge Cases

Empty list

Returns false immediately, no numbers to sum

DSA Go

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

Target is zero

Returns true immediately because sum 0 matches target

DSA Go

if currentSum == target { return true }

Single element equals target

Returns true when that element is chosen

DSA Go

if currentSum == target { return true }

When to Use This Pattern

When a problem requires trying many combinations to find an exact solution and greedy choices fail, backtracking is the pattern to explore all possibilities.

Common Mistakes

Mistake: Using greedy approach and assuming it always finds the solution
Fix: Implement backtracking to explore all combinations when greedy fails

Mistake: Not stopping recursion when sum exceeds target
Fix: Add condition to return false if current sum is greater than target

Summary

Backtracking tries all possible choices to find the exact solution when greedy fails.

Use backtracking when local best choices do not guarantee global best solution.

The key insight is that greedy can miss solutions because it never revisits earlier choices, but backtracking explores all paths.

Practice

1. Why do we need backtracking instead of just using a greedy approach for some problems?

easy

A. Because backtracking only works for sorting problems.

B. Because backtracking always runs faster than greedy algorithms.

C. Because greedy algorithms use more memory than backtracking.

D. Because greedy algorithms make local choices that may not lead to the best overall solution.

Solution

1. Step 1: Understand greedy algorithm behavior

   Greedy algorithms pick the best option at each step without reconsidering previous choices.

2. Step 2: Understand backtracking advantage

   Backtracking tries all possibilities and can undo choices to find the best overall solution.

3. Final Answer:

   Because greedy algorithms make local choices that may not lead to the best overall solution. -> Option D

4. Quick Check:

   Greedy local choice ≠ global best [OK]

Hint: Backtracking explores all options; greedy picks locally best only [OK]

Common Mistakes:

• Thinking greedy is always faster and better
• Confusing memory use between algorithms
• Believing backtracking is only for sorting

2. Which of the following Go code snippets correctly starts a backtracking function signature for solving a problem?

easy

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

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

C. func backtrack() int { }

D. func backtrack(path string) string { }

Solution

1. Step 1: Identify typical backtracking parameters

   Backtracking usually passes the current path (partial solution) and remaining choices as slices.

2. Step 2: Check each function signature

   func backtrack(path []int, choices []int) { } uses slices for path and choices, suitable for backtracking. Others use single values or wrong types.

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
• Returning values when not needed
• Using wrong parameter types

3. What is the output of this Go code snippet that tries to solve the subset sum problem using backtracking?

package main
import "fmt"

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

func main() {
    nums := []int{2, 3, 6, 7}
    backtrack(nums, 7, 0, []int{})
}

medium

A. [2 3 6]
[7]

B. [2 3 7]
[7]

C. [7]

D. [7]
[2 3 6]

Solution

1. Step 1: Understand the problem and code

   The code finds subsets of nums that sum to 7, using backtracking and no repeats.

2. Step 2: Trace the backtracking calls

   Possible subsets: [7] sums to 7; [2,3,6] sums to 11 (too big), so skipped; only [7] prints.

3. Final Answer:

   [7] -> Option C

4. Quick Check:

   Only subset summing to 7 is [7] [OK]

Hint: Check sums carefully; skip subsets exceeding target [OK]

Common Mistakes:

• Assuming [2 3 6] sums to 7
• Confusing order of printed subsets
• Ignoring the continue condition

4. Find the bug in this Go backtracking code snippet that tries to generate all permutations of a slice of integers:

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

medium

A. Missing removal of last element from path after recursion

B. Used slice is not initialized

C. Base case condition is incorrect

D. Loop index should start from 1

Solution

1. Step 1: Analyze backtracking recursion steps

   After recursive call, path must remove last added element to backtrack correctly.

2. Step 2: Identify missing backtracking step

   Code appends to path but never removes last element after recursion, causing incorrect paths.

3. Final Answer:

   Missing removal of last element from path after recursion -> Option A

4. Quick Check:

   Backtracking needs to undo path changes [OK]

Hint: Always undo changes to path after recursive call [OK]

Common Mistakes:

• Forgetting to remove last element from path
• Not initializing used slice before call
• Incorrect base case length check

5. You want to solve the classic N-Queens problem where you place N queens on an NxN chessboard so that no two queens attack each other. Why can't a greedy algorithm solve this correctly, and how does backtracking help?

hard

A. Greedy only works for even N; backtracking works for all N.

B. Greedy places queens row by row without checking future conflicts; backtracking tries all placements and backtracks on conflicts.

C. Greedy uses too much memory; backtracking uses less memory by pruning.

D. Greedy sorts queens by position; backtracking sorts by attack count.

Solution

1. Step 1: Understand greedy limitations for N-Queens

   Greedy tries to place queens row by row choosing first safe spot, but may miss solutions requiring backtracking.

2. Step 2: Understand backtracking approach

   Backtracking tries all possible queen placements, undoing choices when conflicts arise, ensuring all solutions are found.

3. Final Answer:

   Greedy places queens row by row without checking future conflicts; backtracking tries all placements and backtracks on conflicts. -> Option B

4. Quick Check:

   N-Queens needs full search, not greedy local choice [OK]

Hint: N-Queens needs full search; greedy fails on future conflicts [OK]

Common Mistakes:

• Thinking greedy can always find a solution
• Confusing memory use differences
• Believing greedy works only for even N