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

Concept Flow - Why Backtracking and What Greedy Cannot Solve

Start: Problem to solve

↓

Try Greedy Approach

↓

Is solution optimal?

Yes→Done: Use Greedy

No↓

Try Backtracking

↓

Explore all possibilities

↓

Find optimal solution

↓

Done: Use Backtracking

Start with greedy; if it fails to find the best solution, backtracking tries all options to find the optimal one.

Execution Sample

DSA Java

int[] nums = {1, 3, 4};
int target = 6;
// Greedy picks largest <= target repeatedly
// Backtracking tries all combos to sum to target

Shows greedy picking largest numbers first vs backtracking exploring all combinations to reach target sum.

Execution Table

Step	Approach	Current Choice	Remaining Target	Action	Partial Solution	Reasoning
1	Greedy	4	6	Pick 4	[4]	4 <= 6, pick largest
2	Greedy	3	2	Skip 3	[4]	3 > remaining 2, skip
3	Greedy	1	2	Pick 1	[4,1]	1 <= 2, pick
4	Greedy	1	1	Pick 1	[4,1,1]	1 <= 1, pick
5	Greedy	-	0	Done	[4,1,1]	Sum 6 reached but not minimal count
6	Backtracking	Try 1	6	Choose 1	[1]	Try all combos
7	Backtracking	Try 3	5	Choose 3	[1,3]	Continue exploring
8	Backtracking	Try 1	2	Choose 1	[1,3,1]	Continue exploring
9	Backtracking	Try 1	1	Choose 1	[1,3,1,1]	Sum 6 reached
10	Backtracking	Backtrack	-	Remove last 1	[1,3,1]	Try other options
11	Backtracking	Try 4	2	Skip 4	[1,3,1]	4 > 2 skip
12	Backtracking	Backtrack	-	Remove 1	[1,3]	Try other options
13	Backtracking	Try 3	3	Choose 3	[1,3,3]	Sum 7 > 6 skip
14	Backtracking	Backtrack	-	Remove 3	[1,3]	Try other options
15	Backtracking	Backtrack	-	Remove 3	[1]	Try other options
16	Backtracking	Try 4	5	Choose 4	[1,4]	Continue exploring
17	Backtracking	Try 1	1	Choose 1	[1,4,1]	Sum 6 reached
18	Backtracking	Done	-	Found solution	[1,4,1]	Optimal solution found
19	Backtracking	Try 3	2	Skip 3	[1,4]	3 > 2 skip
20	Backtracking	Backtrack	-	Remove 1	[1,4]	Try other options
21	Backtracking	Backtrack	-	Remove 4	[1]	Try other options
22	Backtracking	Backtrack	-	Remove 1	[]	Try other options
23	Backtracking	Try 3	6	Choose 3	[3]	Try all combos
24	Backtracking	Try 3	3	Choose 3	[3,3]	Sum 6 reached
25	Backtracking	Done	-	Found solution	[3,3]	Optimal solution found
26	Backtracking	Try 4	6	Choose 4	[4]	Try all combos
27	Backtracking	Try 1	2	Choose 1	[4,1]	Continue exploring
28	Backtracking	Try 1	1	Choose 1	[4,1,1]	Sum 6 reached
29	Backtracking	Done	-	Found solution	[4,1,1]	Solution found but not minimal count
30	Backtracking	End	-	All combos tried	[]	Backtracking complete

💡 Greedy stops early with suboptimal solution; backtracking explores all combos to find optimal.

Variable Tracker

Variable	Start	Step 1	Step 6	Step 18	Step 25	Final
Partial Solution	[]	[4]	[1]	[1,4,1]	[3,3]	[]
Remaining Target	6	2	1	0	0	6
Approach	None	Greedy	Backtracking	Backtracking	Backtracking	Backtracking

Key Moments - 3 Insights

Why does greedy pick [4,1,1] instead of [3,3] which is better?

Greedy picks the largest number <= remaining target at each step without looking ahead (see steps 1-5). It stops early with a suboptimal solution. Backtracking tries all combos (steps 6-30) and finds [3,3] which is optimal.

Why does backtracking try removing last choice and try others?

Backtracking explores all possibilities by undoing (backtracking) previous choices to try alternatives (see steps 10, 12, 14, 20, 21, 22). This ensures no solution is missed.

When does backtracking stop exploring?

Backtracking stops after trying all combinations and finding all solutions (step 30). It ensures the optimal solution is found by exhaustive search.

Visual Quiz - 3 Questions

Look at the execution table, what partial solution does greedy have at step 5?

A [1,3,1]

B [3,3]

C [4,1,1]

D [1,4,1]

💡 Hint

Check the 'Partial Solution' column at step 5 in the execution_table.

At which step does backtracking first find a solution summing to target 6?

A Step 9

B Step 18

C Step 25

D Step 29

💡 Hint

Look for 'Sum 6 reached' in the 'Reasoning' column for backtracking steps.

If greedy tried picking 3 first instead of 4, how would the partial solution at step 5 change?

A [4,1,1]

B [3,3]

C [1,3,1]

D [3,1,1]

💡 Hint

Consider greedy picking largest <= target repeatedly; picking 3 first leads to [3,3] sum 6.

Concept Snapshot

Greedy picks locally best choices fast but may miss optimal.
Backtracking tries all options by exploring and undoing choices.
Use backtracking when greedy fails to find best solution.
Backtracking is slower but guarantees optimality.
Greedy is efficient but not always correct.
Choose approach based on problem nature.

Full Transcript

This visualization compares greedy and backtracking approaches solving a target sum problem. Greedy picks the largest number less than or equal to the remaining target at each step, quickly reaching a solution but not always the best one. Backtracking tries all possible combinations by choosing numbers, checking sums, and undoing choices to explore alternatives. The execution table shows greedy stopping early with a suboptimal solution [4,1,1], while backtracking finds the optimal [3,3]. Variable tracking shows how partial solutions and remaining targets change. Key moments clarify why greedy fails and how backtracking explores all possibilities. The quiz tests understanding of these steps. In summary, greedy is fast but may fail; backtracking is thorough and finds the best solution by exploring all options.

Practice

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

easy

A. Because backtracking explores all possible solutions and can backtrack when stuck

B. Because greedy algorithms always find the best solution quickly

C. Because backtracking uses less memory than greedy algorithms

D. Because greedy algorithms do not use recursion

Solution

1. Step 1: Understand problem requirements

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

2. Step 2: Compare algorithm approaches

   Backtracking tries all options and can undo choices if they lead to conflicts, while greedy picks immediate best without reconsidering.

3. Final Answer:

   Because backtracking explores all possible solutions and can backtrack when stuck -> Option A

4. Quick Check:

   Backtracking explores all possible solutions and can backtrack when stuck = C [OK]

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

Common Mistakes:

• Thinking greedy always finds the best solution
• Confusing backtracking with greedy memory use
• Assuming greedy uses recursion like backtracking

2. Which of the following is the correct syntax to start a backtracking function in Java for solving a problem recursively?

easy

A. function backtrack(step) { ... }

B. void backtrack() = { ... }

C. public backtrack(int step) { ... }

D. public void backtrack(int step, List<Integer> path) { ... }

Solution

1. Step 1: Identify valid Java method syntax

   Java methods require return type, method name, parameters in parentheses, and braces for body.

2. Step 2: Check each option

   public void backtrack(int step, List<Integer> path) { ... } uses correct Java syntax with return type void, method name, parameters, and braces.

3. Final Answer:

   public void backtrack(int step, List<Integer> path) { ... } -> Option D

4. Quick Check:

   Java method syntax = A [OK]

Hint: Java methods need return type and parentheses [OK]

Common Mistakes:

• Using '=' instead of braces for method body
• Omitting return type in method declaration
• Using JavaScript syntax in Java code

3. What will be the output of the following Java code snippet that uses backtracking to print all subsets of {1, 2}?

public class Subsets {
  public static void backtrack(int[] nums, int start, List<Integer> temp, List res) {
    res.add(new ArrayList<>(temp));
    for (int i = start; i < nums.length; i++) {
      temp.add(nums[i]);
      backtrack(nums, i + 1, temp, res);
      temp.remove(temp.size() - 1);
    }
  }
  public static void main(String[] args) {
    int[] nums = {1, 2};
    List res = new ArrayList<>();
    backtrack(nums, 0, new ArrayList<>(), res);
    System.out.println(res);
  }
}

medium

A. [[], [1], [1, 2], [2]]

B. [[1], [2], [1, 2]]

C. [[], [2], [1]]

D. [[1, 2]]

Solution

1. Step 1: Understand backtracking for subsets

   The method adds current subset, then tries adding each next element recursively, then removes it to backtrack.

2. Step 2: Trace output for nums = {1, 2}

   Subsets generated: [] (empty), [1], [1, 2], and [2].

3. Final Answer:

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

4. Quick Check:

   All subsets of {1,2} = B [OK]

Hint: Backtracking lists all subsets including empty [OK]

Common Mistakes:

• Missing empty subset in output
• Not including subsets in correct order
• Confusing subsets with permutations

4. The following backtracking code is intended to find all permutations of {1, 2}, but it has a bug. What is the bug?

public static void backtrack(List<Integer> nums, List<Integer> temp, List res) {
  if (temp.size() == nums.size()) {
    res.add(new ArrayList<>(temp));
    return;
  }
  for (int i = 0; i < nums.size(); i++) {
    temp.add(nums.get(i));
    backtrack(nums, temp, res);
    temp.remove(temp.size() - 1);
  }
}

medium

A. It does not call backtrack recursively

B. It uses wrong base case size comparison

C. It does not check if element is already in temp, causing duplicates

D. It removes elements before adding them

Solution

1. Step 1: Analyze recursion and element addition

   The code adds elements without checking if they are already in temp, so duplicates appear in permutations.

2. Step 2: Identify missing condition

   Backtracking for permutations must skip elements already used in temp to avoid repeated elements.

3. Final Answer:

   It does not check if element is already in temp, causing duplicates -> Option C

4. Quick Check:

   Missing used-element check = D [OK]

Hint: Check if element already used before adding [OK]

Common Mistakes:

• Ignoring duplicate elements in permutations
• Confusing base case with wrong size
• Thinking recursion is missing

5. Given the problem of selecting a subset of items with weights and values to maximize value without exceeding a weight limit, why can't a greedy algorithm always solve this correctly, and how does backtracking help?

hard

A. Greedy always finds best solution quickly; backtracking is slower but simpler

B. Greedy picks locally best items but may miss best total; backtracking tries all combinations

C. Greedy uses recursion; backtracking uses loops only

D. Greedy requires sorting; backtracking does not

Solution

1. Step 1: Understand greedy approach limitation

   Greedy picks items with best value/weight ratio first, but this may miss combinations with better total value.

2. Step 2: Explain backtracking advantage

   Backtracking tries all subsets, ensuring the best total value is found by exploring all possibilities.

3. Final Answer:

   Greedy picks locally best items but may miss best total; backtracking tries all combinations -> Option B

4. Quick Check:

   Greedy local vs backtracking global = A [OK]

Hint: Greedy misses global best; backtracking tries all [OK]

Common Mistakes:

• Assuming greedy always finds best solution
• Confusing recursion with iteration
• Thinking sorting solves all problems