Why Backtracking and What Greedy Cannot Solve in DSA Java - Test Your Knowledge

Practice - 5 Tasks

1fill in blank

easy

Complete the code to check if a subset sum equals target using backtracking.

DSA Java

boolean subsetSum(int[] nums, int target, int index) {
    if (target == 0) return true;
    if (index == nums.length || target < 0) return false;
    // Choose to include nums[index]
    if (subsetSum(nums, target - nums[index], index + 1)) return true;
    // Choose to exclude nums[index]
    return subsetSum(nums, target, [1]);
}

Drag options to blanks, or click blank then click option'

Aindex - 1

Bindex + 1

Ctarget + 1

Dnums.length

Attempts:

3 left

💡 Hint

Common Mistakes

Using index - 1 causes infinite recursion or wrong checks.

Using target + 1 is incorrect because target is not an index.

We move to the next index when excluding the current number, so index + 1 is correct.

2fill in blank

medium

Complete the code to find the maximum sum of non-adjacent elements using greedy approach.

DSA Java

int maxSumNonAdjacent(int[] nums) {
    int incl = 0, excl = 0;
    for (int num : nums) {
        int new_excl = Math.max(incl, excl);
        incl = excl + num;
        excl = [1];
    }
    return Math.max(incl, excl);
}

Drag options to blanks, or click blank then click option'

Aincl

Bnum

Cnew_excl

Dexcl

Attempts:

3 left

💡 Hint

Common Mistakes

Assigning excl to incl causes wrong sums.

Assigning excl to num is incorrect as num is current element.

We update excl to new_excl which holds the max of previous incl and excl.

3fill in blank

hard

Fix the error in the backtracking code to generate all subsets.

DSA Java

void generateSubsets(int[] nums, int index, List<Integer> current, List<List<Integer>> result) {
    if (index == nums.length) {
        result.add(new ArrayList<>(current));
        return;
    }
    // Include nums[index]
    current.add(nums[index]);
    generateSubsets(nums, index + 1, current, result);
    // Exclude nums[index]
    [1];
    generateSubsets(nums, index + 1, current, result);
}

Drag options to blanks, or click blank then click option'

Acurrent.remove(current.size() - 1)

Bcurrent.add(nums[index])

Cresult.clear()

Dindex--

Attempts:

3 left

💡 Hint

Common Mistakes

Not removing the element causes wrong subsets with duplicates.

Clearing result or changing index incorrectly breaks logic.

We must remove the last added element before exploring exclusion path to avoid duplicates.

4fill in blank

hard

Fill both blanks to create a backtracking solution that finds all permutations of a string.

DSA Java

void permute(String str, String chosen, List<String> result) {
    if (str.length() == 0) {
        result.add(chosen);
    } else {
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            String rest = str.substring(0, [1]) + str.substring([2]);
            permute(rest, chosen + c, result);
        }
    }
}

Drag options to blanks, or click blank then click option'

Ai

Bi + 1

Ci - 1

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using i-1 causes errors as negative index is invalid.

Using 0 for both blanks does not remove the character.

We remove the character at index i by taking substring before i and after i+1.

5fill in blank

hard

Fill all three blanks to implement a greedy algorithm to select intervals with maximum non-overlapping intervals.

DSA Java

List<Interval> selectIntervals(List<Interval> intervals) {
    Collections.sort(intervals, (a, b) -> a.[1] - b.[1]);
    List<Interval> result = new ArrayList<>();
    int end = Integer.MIN_VALUE;
    for (Interval interval : intervals) {
        if (interval.[2] >= end) {
            result.add(interval);
            end = interval.[3];
        }
    }
    return result;
}

Drag options to blanks, or click blank then click option'

Aend

Bstart

Cfinish

Dlength

Attempts:

3 left

💡 Hint

Common Mistakes

Sorting by start or length changes the greedy strategy.

Using wrong fields for comparison causes incorrect selections.

We sort intervals by finish time, check if current start >= last end, then update end to current finish.

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