Why Backtracking and What Greedy Cannot Solve in DSA Python - 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 dishes at a buffet: greedy means picking your favorite dish first without thinking about the whole meal, but backtracking means trying different combinations of dishes to find the tastiest full meal.

Start
  ↓
Choice 1 -> Choice 2 -> Choice 3 -> ...
  ↓        ↓        ↓
Try all paths to find best

Dry Run Walkthrough

Input: Find subset of numbers [3, 1, 7, 9] that sums to 10

Goal: Show greedy finds a subset summing to 10 (9+1), backtracking finds [3,7]; greedy may fail in other cases

Step 1: Greedy picks largest number ≤ 10: picks 9

Chosen: 9, Remaining sum to reach: 1

Why: Greedy picks biggest number first to get close to target quickly

Step 2: Greedy tries to pick next largest ≤ 1: picks 1

Chosen: 9 -> 1, Sum: 10

Why: Greedy thinks sum is reached, and 9 + 1 = 10 is correct here

Step 3: Backtracking tries subsets starting empty

[]

Why: Backtracking explores all subsets to find sum 10

Step 4: Backtracking tries [3], sum=3 < 10, continue

[3]

Why: Try including 3

Step 5: Backtracking tries [3,1], sum=4 < 10, continue

[3 -> 1]

Why: Try adding 1

Step 6: Backtracking tries [3,1,7], sum=11 > 10, backtrack

[3 -> 1 -> 7]

Why: Sum exceeded, discard this path

Step 7: Backtracking tries [3,1,9], sum=13 > 10, backtrack

[3 -> 1 -> 9]

Why: Sum exceeded, discard

Step 8: Backtracking tries [3,7], sum=10 found, success

[3 -> 7]

Why: Found subset summing exactly to 10

Result:

Backtracking finds subset: 3 -> 7 -> null
Greedy found subset: 9 -> 1 -> null (also sum 10 but may fail in other cases)

Annotated Code

DSA Python

class BacktrackingSubsetSum:
    def __init__(self, nums, target):
        self.nums = nums
        self.target = target
        self.result = []

    def backtrack(self, start, path, current_sum):
        if current_sum == self.target:
            self.result = path.copy()
            return True
        if current_sum > self.target:
            return False
        for i in range(start, len(self.nums)):
            path.append(self.nums[i])
            if self.backtrack(i + 1, path, current_sum + self.nums[i]):
                return True
            path.pop()
        return False

class GreedySubsetSum:
    def __init__(self, nums, target):
        self.nums = sorted(nums, reverse=True)
        self.target = target
        self.result = []

    def greedy(self):
        total = 0
        for num in self.nums:
            if total + num <= self.target:
                self.result.append(num)
                total += num
            if total == self.target:
                break
        return total == self.target

# Driver code
nums = [3, 1, 7, 9]
target = 10

# Greedy approach
greedy_solver = GreedySubsetSum(nums, target)
greedy_found = greedy_solver.greedy()
print("Greedy subset:", " -> ".join(map(str, greedy_solver.result)) + " -> null" if greedy_found else "No subset found")

# Backtracking approach
backtrack_solver = BacktrackingSubsetSum(nums, target)
backtrack_found = backtrack_solver.backtrack(0, [], 0)
if backtrack_found:
    print("Backtracking subset:", " -> ".join(map(str, backtrack_solver.result)) + " -> null")
else:
    print("No subset found")

if current_sum == self.target:

check if current subset sums exactly to target

if current_sum > self.target:

stop exploring path if sum exceeded target

for i in range(start, len(self.nums)):

try each number starting from current index

path.append(self.nums[i])

include current number in subset

if self.backtrack(i + 1, path, current_sum + self.nums[i]):

recurse to next number with updated sum

path.pop()

remove last number to backtrack and try other options

if total + num <= self.target:

greedy picks number only if it doesn't exceed target

if total == self.target:

stop if target sum reached

Output

Greedy subset: 9 -> 1 -> null

Backtracking subset: 3 -> 7 -> null

Complexity Analysis

Time: Backtracking: O(2^n) because it tries all subsets; Greedy: O(n log n) due to sorting and single pass

Space: Backtracking: O(n) for recursion stack and path; Greedy: O(n) for result storage

vs Alternative: Backtracking is slower but finds correct solution always; greedy is faster but can fail on some inputs

Edge Cases

Empty list

Backtracking returns no subset; greedy returns no subset

DSA Python

if current_sum == self.target:

Target sum zero

Backtracking returns empty subset as valid; greedy returns empty subset

DSA Python

if current_sum == self.target:

No subset sums to target

Backtracking explores all and returns no subset; greedy returns partial or no subset

DSA Python

return False

When to Use This Pattern

When a problem requires exploring all combinations or subsets to find a solution and greedy choices fail, use backtracking to try all possibilities systematically.

Common Mistakes

Mistake: Assuming greedy always finds correct subset sum
Fix: Use backtracking to verify or find correct subset when greedy fails

Mistake: Not backtracking (undoing) after exploring a path
Fix: Always remove last choice before trying next to explore all options

Summary

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

Use backtracking when greedy's local best choices do not guarantee a global best solution.

The key insight is that greedy looks only at immediate best choice, while backtracking explores all paths to find the true solution.

Practice

1. Why is backtracking preferred over greedy algorithms in problems like the N-Queens puzzle?

easy

A. Because greedy algorithms never use recursion

B. Because greedy algorithms always find the optimal solution quickly

C. Because backtracking uses less memory than greedy algorithms

D. Because backtracking explores all possible solutions and can backtrack on wrong choices

Solution

1. Step 1: Understand the problem nature

   The N-Queens puzzle requires placing queens so none attack each other, needing exploration of many possibilities.

2. Step 2: Compare backtracking and greedy approaches

   Backtracking tries all options and undoes wrong choices, while greedy picks locally best choices that may fail globally.

3. Final Answer:

   Because backtracking explores all possible solutions and can backtrack on wrong choices -> Option D

4. Quick Check:

   Backtracking explores all options = A [OK]

Hint: Backtracking tries all paths; greedy picks only best immediate choice [OK]

Common Mistakes:

• Thinking greedy always finds the best solution
• Confusing backtracking with dynamic programming
• Assuming backtracking uses less memory

2. Which of the following is the correct syntax to start a backtracking function in Python?

easy

A. def backtrack(path, options):

B. function backtrack(path, options) {

C. backtrack(path, options) => {

D. def backtrack[]:

Solution

1. Step 1: Identify Python function syntax

   Python functions start with 'def', followed by name and parameters in parentheses, ending with a colon.

2. Step 2: Check each option

   def backtrack[]: uses invalid square brackets instead of parentheses; function backtrack(path, options) { and backtrack(path, options) => { are JavaScript syntax; def backtrack(path, options): is the correct Python syntax.

3. Final Answer:

   def backtrack(path, options): -> Option A

4. Quick Check:

   Python function syntax = D [OK]

Hint: Python functions start with 'def' and end with ':' [OK]

Common Mistakes:

• Using JavaScript or other language syntax
• Missing colon at function end
• Using square brackets instead of parentheses

3. What will be the output of the following Python code snippet?

def backtrack(nums, path):
    if not nums:
        print(path)
        return
    for i in range(len(nums)):
        backtrack(nums[:i] + nums[i+1:], path + [nums[i]])

backtrack([1, 2], [])

medium

A. [2, 1]

B. [1, 2]

C. [1, 2]\n[2, 1]

D. []

Solution

1. Step 1: Understand the backtracking function

   The function generates all permutations of the list by choosing each element and recursing on the rest.

2. Step 2: Trace the calls for input [1, 2]

   First call picks 1, then 2 left, prints [1, 2]. Second call picks 2, then 1 left, prints [2, 1].

3. Final Answer:

   [1, 2] [2, 1] -> Option C

4. Quick Check:

   Permutations of [1, 2] = [1, 2] and [2, 1] [OK]

Hint: Backtracking here prints all permutations of the list [OK]

Common Mistakes:

• Thinking it prints only one permutation
• Confusing slicing syntax
• Missing that print happens when nums is empty

4. Find the error in this backtracking code for subset generation:

def subsets(nums, path=[]):
    print(path)
    for i in range(len(nums)):
        subsets(nums[i+1:], path.append(nums[i]))

subsets([1, 2])

medium

A. Using mutable default argument for path causes unexpected behavior

B. Missing return statement in function

C. Incorrect slicing of nums in recursive call

D. Using print inside recursion is invalid

Solution

1. Step 1: Identify mutable default argument issue

   Using path=[] as default causes the same list to be shared across calls, leading to wrong subsets.

2. Step 2: Check recursive call usage

   path.append(nums[i]) modifies path in place and returns None, so recursive call gets None instead of list.

3. Final Answer:

   Using mutable default argument for path causes unexpected behavior -> Option A

4. Quick Check:

   Mutable default args cause bugs = A [OK]

Hint: Avoid mutable defaults like lists in function parameters [OK]

Common Mistakes:

• Ignoring mutable default argument problem
• Thinking print inside recursion is wrong
• Assuming missing return causes error here

5. Which problem below cannot be solved correctly by a greedy algorithm but requires backtracking to find all solutions?

A) Finding minimum number of coins for change when coin denominations are unlimited and standard
B) Finding all subsets of a set
C) Finding shortest path in a weighted graph with non-negative edges
D) Sorting an array in ascending order

hard

A. Finding minimum number of coins for change when coin denominations are unlimited and standard

B. Finding all subsets of a set

C. Finding shortest path in a weighted graph with non-negative edges

D. Sorting an array in ascending order

Solution

1. Step 1: Analyze each problem type

   A) Greedy works for standard coin change; C) Dijkstra's algorithm is greedy and works; D) Sorting uses greedy-like comparisons.

2. Step 2: Identify problem needing backtracking

   Finding all subsets requires exploring all combinations, which greedy cannot do; backtracking is needed.

3. Final Answer:

   Finding all subsets of a set -> Option B

4. Quick Check:

   All subsets need backtracking = B [OK]

Hint: All subsets require exploring all options, not greedy choice [OK]

Common Mistakes:

• Thinking greedy can find all subsets
• Confusing shortest path with subset generation
• Assuming sorting needs backtracking