Why Backtracking and What Greedy Cannot Solve in DSA Java - 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, backtracking means trying different combinations of dishes to find the tastiest full meal.

Start
  ↓
Choice 1 -> Choice 2 -> Choice 3 -> ...
  ↓        ↓        ↓
Backtrack if needed ←←←

Dry Run Walkthrough

Input: Set: {3, 4, 5}, Target sum: 7

Goal: Find all subsets that sum to 7 using backtracking and show why greedy fails

Step 1: Start with empty subset []

[]

Why: We begin with no elements chosen

Step 2: Add 3 to subset: [3]

[3]

Why: Try first element to see if it leads to target

Step 3: Add 4 to subset: [3, 4]

[3, 4]

Why: Add next element to approach target sum

Step 4: Sum is 7 == 7, record subset [3, 4]

[3, 4]

Why: Found a subset that matches target sum

Step 5: Backtrack by removing 4: [3]

[3]

Why: After solution, backtrack to try other options

Step 6: Add 5 to subset: [3, 5]

[3, 5]

Why: Try next element

Step 7: Sum is 8 > 7, backtrack by removing 5: [3]

[3]

Why: Sum exceeded target, so remove last choice

Step 8: Backtrack by removing 3: []

[]

Why: Try other combinations without 3

Step 9: Add 4 to subset: [4]

[4]

Why: Try next starting element

Step 10: Add 5 to subset: [4, 5]

[4, 5]

Why: Try adding next element

Step 11: Sum is 9 > 7, backtrack by removing 5: [4]

[4]

Why: Sum exceeded target, remove last choice

Step 12: Backtrack to empty subset and try adding 5: [5]

[5]

Why: Try last starting element

Step 13: Sum is 5 < 7, no more elements to add, backtrack

[5]

Why: Cannot reach target from here

Result:

Subsets that sum to 7: [3, 4]

Greedy approach picks 5 first (largest), then tries to add 4 (sum 9 > 7), skips, tries to add 3 (sum 8 > 7), fails with sum=5, misses [3, 4] solution.

Annotated Code

DSA Java

import java.util.ArrayList;
import java.util.List;

public class BacktrackingExample {

    public static void findSubsets(int[] set, int target) {
        List<Integer> current = new ArrayList<>();
        backtrack(set, target, 0, current);
    }

    private static void backtrack(int[] set, int target, int start, List<Integer> current) {
        int sum = current.stream().mapToInt(Integer::intValue).sum();
        if (sum == target) {
            System.out.println(current);
            // Removed return here to find all solutions
        }
        if (sum > target) {
            return; // stop exploring this path
        }
        for (int i = start; i < set.length; i++) {
            current.add(set[i]); // choose
            backtrack(set, target, i + 1, current); // explore
            current.remove(current.size() - 1); // un-choose (backtrack)
        }
    }

    public static void main(String[] args) {
        int[] set = {3, 4, 5};
        int target = 7;
        System.out.println("Subsets that sum to " + target + ":");
        findSubsets(set, target);

        // Demonstrate greedy failure
        System.out.println("\nGreedy approach attempt:");
        greedyAttempt(set, target);
    }

    private static void greedyAttempt(int[] set, int target) {
        int sum = 0;
        List<Integer> chosen = new ArrayList<>();
        // Greedy: pick largest first
        for (int i = set.length - 1; i >= 0; i--) {
            if (sum + set[i] <= target) {
                chosen.add(set[i]);
                sum += set[i];
            }
        }
        System.out.println(chosen + " sum=" + sum);
    }
}

int sum = current.stream().mapToInt(Integer::intValue).sum();

Calculate current subset sum to check against target

if (sum == target) { System.out.println(current); /* Removed return here to find all solutions */ }

If sum matches target, print subset and continue exploring to find all solutions

if (sum > target) { return; }

If sum exceeds target, stop exploring this path (prune)

for (int i = start; i < set.length; i++) { current.add(set[i]); backtrack(set, target, i + 1, current); current.remove(current.size() - 1); }

Try each element from start index, recurse, then backtrack by removing last element

for (int i = set.length - 1; i >= 0; i--) { if (sum + set[i] <= target) { chosen.add(set[i]); sum += set[i]; } }

Greedy picks largest elements first if they don't exceed target

Output

Subsets that sum to 7:

[3, 4]



Greedy approach attempt:

[5] sum=5

Complexity Analysis

Time: O(2^n) because backtracking explores all subsets in worst case

Space: O(n) for recursion stack and current subset storage

vs Alternative: Greedy runs in O(n) but can miss correct solutions because it doesn't explore all options

Edge Cases

Empty set

No subsets found, no output

DSA Java

for (int i = start; i < set.length; i++) { ... }

Target sum zero

Empty subset matches target and is printed

DSA Java

if (sum == target) { System.out.println(current); /* Removed return here to find all solutions */ }

No subset sums to target

No output subsets, backtracking explores all and ends

DSA Java

if (sum > target) { return; }

When to Use This Pattern

When a problem requires trying many combinations to find all or the best solution, and greedy choices fail, backtracking is the right pattern to explore all possibilities systematically.

Common Mistakes

Mistake: Stopping after first valid subset without exploring others
Fix: Remove return after printing subset to find all solutions

Mistake: Not backtracking (removing last choice) after recursion
Fix: Always remove last added element after recursive call to explore other paths

Summary

Backtracking tries all possible choices step-by-step to find solutions that greedy misses.

Use backtracking when greedy fails because the problem requires exploring many combinations.

The key insight is that greedy picks locally best choices, but backtracking explores all to find the global best.

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