Why Backtracking and What Greedy Cannot Solve in DSA Python - Why It Works

Concept Flow - Why Backtracking and What Greedy Cannot Solve

Start with problem

↓

Try Greedy choice

↓

Is solution valid and optimal?

Yes→Done

No↓

Backtrack: Undo last choice

↓

Try next choice

↓

Repeat until all choices tried or solution found

Shows how greedy tries one choice and stops if optimal, but backtracking tries all choices by undoing and retrying.

Execution Sample

DSA Python

def backtrack(path, choices):
    if complete(path):
        print(path)
        return
    for c in choices:
        if valid(path, c):
            backtrack(path + [c], choices)

Backtracking tries all valid choices recursively to find all solutions.

Execution Table

Step	Operation	Current Path	Choice Tried	Action	Visual State
1	Start	[]	-	Begin with empty path	[]
2	Try choice 1	[]	1	Add 1 to path	[1]
3	Try choice 2	[1]	2	Add 2 to path	[1, 2]
4	Complete?	[1, 2]	-	No, continue	[1, 2]
5	Try choice 3	[1, 2]	3	Add 3 to path	[1, 2, 3]
6	Complete?	[1, 2, 3]	-	Yes, print path	[1, 2, 3]
7	Backtrack	[1, 2, 3]	-	Remove 3, try next choice	[1, 2]
8	No more choices	[1, 2]	-	Backtrack again	[1]
9	Try choice 3	[1]	3	Add 3 to path	[1, 3]
10	Complete?	[1, 3]	-	No, continue	[1, 3]
11	Backtrack	[1, 3]	-	Remove 3, no more choices	[1]
12	Backtrack	[1]	-	Remove 1, try next choice	[]
13	Try choice 2	[]	2	Add 2 to path	[2]
14	Try choice 3	[2]	3	Add 3 to path	[2, 3]
15	Complete?	[2, 3]	-	Yes, print path	[2, 3]
16	Backtrack	[2, 3]	-	Remove 3, no more choices	[2]
17	Backtrack	[2]	-	Remove 2, try next choice	[]
18	Try choice 3	[]	3	Add 3 to path	[3]
19	Complete?	[3]	-	No, no more choices	[3]
20	Backtrack	[3]	-	Remove 3, no more choices	[]
21	End	[]	-	All choices tried	[]

💡 All possible paths tried by backtracking, no more choices left.

Variable Tracker

Variable	Start	After Step 2	After Step 5	After Step 7	After Step 9	After Step 12	After Step 15	After Step 20	Final
path	[]	[1]	[1, 2, 3]	[1, 2]	[1, 3]	[]	[2, 3]	[]	[]
choice	-	1	3	-	3	2	3	3	-

Key Moments - 3 Insights

Why can't greedy always find the best solution?

Greedy picks the best immediate choice but may miss better overall solutions, as shown in steps 2-6 where greedy choice leads to partial path but backtracking explores all paths (execution_table rows 2-21).

How does backtracking undo choices?

Backtracking removes the last choice to try alternatives, seen in steps 7, 11, 16, and 20 where path shrinks to explore new options (execution_table rows 7, 11, 16, 20).

What happens if no valid choices remain?

Backtracking continues removing choices until all options are tried or solution found, ending at step 21 when path is empty and no choices left (execution_table row 21).

Visual Quiz - 3 Questions

Look at the execution table, what is the path after step 5?

A [1, 2]

B [1, 2, 3]

C [1, 3]

D [2, 3]

💡 Hint

Check the 'Current Path' column at step 5 in the execution_table.

At which step does backtracking first remove a choice from the path?

A Step 7

B Step 9

C Step 6

D Step 12

💡 Hint

Look for 'Backtrack' action and path shrinking in execution_table rows.

If greedy was used instead of backtracking, which step would it stop at?

A Step 21

B Step 15

C Step 6

D Step 12

💡 Hint

Greedy stops at first complete solution found, see step 6 in execution_table.

Concept Snapshot

Backtracking tries all choices by exploring and undoing steps.
Greedy picks best immediate choice but can miss solutions.
Backtracking explores full solution space.
Use backtracking when greedy fails.
Backtracking uses recursion and undo steps.
Greedy is faster but less complete.

Full Transcript

Backtracking is a method to find all possible solutions by trying choices one by one, and undoing them if they don't lead to a solution. Greedy algorithms pick the best immediate choice but can miss better overall solutions. The execution table shows how backtracking explores all paths by adding choices to the path, checking if complete, and removing choices to try alternatives. This process continues until all choices are tried. Key moments include understanding why greedy can fail, how backtracking undoes choices, and what happens when no choices remain. The visual quiz tests understanding of path states and backtracking steps. Backtracking is essential when greedy cannot guarantee the best 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