Why Backtracking and What Greedy Cannot Solve in DSA Java - Challenge Your Understanding

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Backtracking Subset Sum Example

What is the output of the following Java code that uses backtracking to find subsets summing to 5?

DSA Java

import java.util.*;
public class SubsetSum {
    static void findSubsets(int[] nums, int target, int index, List<Integer> current, List<List<Integer>> result) {
        if (target == 0) {
            result.add(new ArrayList<>(current));
            return;
        }
        if (target < 0 || index == nums.length) {
            return;
        }
        // Include nums[index]
        current.add(nums[index]);
        findSubsets(nums, target - nums[index], index + 1, current, result);
        // Exclude nums[index]
        current.remove(current.size() - 1);
        findSubsets(nums, target, index + 1, current, result);
    }
    public static void main(String[] args) {
        int[] nums = {2, 3, 5};
        List<List<Integer>> result = new ArrayList<>();
        findSubsets(nums, 5, 0, new ArrayList<>(), result);
        for (List<Integer> subset : result) {
            System.out.println(subset);
        }
    }
}

A [[2, 3], [5]]

B [[2, 3]]

C [[5]]

D []

💡 Hint

Think about all subsets of {2,3,5} that add up exactly to 5.

The code explores all subsets using backtracking. It finds two subsets that sum to 5: [2, 3] and [5].

🧠 Conceptual

intermediate

Why Greedy Fails for Subset Sum

Why does a greedy approach fail to solve the subset sum problem correctly in all cases?

A Because greedy picks local best choices that may not lead to a global solution.

B Because greedy always finds the global solution instantly.

C Because greedy uses backtracking internally.

D Because greedy sorts the input array before processing.

💡 Hint

Consider if picking the largest number first always works.

Greedy algorithms pick the best immediate option but can miss combinations that require skipping some choices to reach the target sum.

❓ Predict Output

advanced

Output of Greedy Coin Change Example

What is the output of this Java code using a greedy approach to make change for 30 cents with coins {25, 10, 5}?

DSA Java

import java.util.*;
public class GreedyCoinChange {
    public static void main(String[] args) {
        int[] coins = {25, 10, 5};
        int amount = 30;
        List<Integer> result = new ArrayList<>();
        for (int coin : coins) {
            while (amount >= coin) {
                amount -= coin;
                result.add(coin);
            }
        }
        System.out.println(result);
    }
}

A [5, 5, 5, 5, 5, 5]

B [10, 10, 10]

C [25, 5]

D [25, 10]

💡 Hint

Greedy picks the largest coin first until it can't.

The greedy approach picks 25 first, then 5 to make 30 cents.

🧠 Conceptual

advanced

Backtracking vs Greedy: Which Solves N-Queens?

Why is backtracking suitable for solving the N-Queens problem but greedy is not?

A Because greedy always places queens in the first available spot without checking conflicts.

B Because N-Queens requires exploring all possible placements to avoid conflicts, which greedy cannot guarantee.

C Because backtracking uses sorting which greedy does not.

D Because greedy solves N-Queens in polynomial time.

💡 Hint

Think about the need to undo choices when conflicts arise.

Backtracking tries all placements and backtracks on conflicts, ensuring a valid solution. Greedy cannot undo wrong choices.

🔧 Debug

expert

Identify the Output of Backtracking Maze Solver

What is the printed path output of this Java backtracking maze solver code?

DSA Java

import java.util.*;
public class MazeSolver {
    static int[][] maze = {
        {1, 0, 0, 0},
        {1, 1, 0, 1},
        {0, 1, 0, 0},
        {1, 1, 1, 1}
    };
    static int N = 4;
    static List<String> path = new ArrayList<>();
    static boolean solve(int x, int y) {
        if (x == N - 1 && y == N - 1) {
            path.add("(" + x + "," + y + ")");
            return true;
        }
        if (x >= 0 && y >= 0 && x < N && y < N && maze[x][y] == 1) {
            maze[x][y] = -1; // mark visited
            path.add("(" + x + "," + y + ")");
            if (solve(x + 1, y)) return true;
            if (solve(x, y + 1)) return true;
            path.remove(path.size() - 1);
            maze[x][y] = 1; // unmark
        }
        return false;
    }
    public static void main(String[] args) {
        if (solve(0, 0)) {
            System.out.println(path);
        } else {
            System.out.println("No path found");
        }
    }
}

A No path found

B [(0,0), (1,0), (1,1), (1,2), (2,2), (3,2), (3,3)]

C [(0,0), (0,1), (1,1), (2,1), (3,1), (3,2), (3,3)]

D [(0,0), (1,0), (1,1), (2,1), (3,1), (3,2), (3,3)]

💡 Hint

The solver tries down first, then right.

The solver moves down when possible, then right. It finds the path through (0,0),(1,0),(1,1),(2,1),(3,1),(3,2),(3,3).

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