Backtracking Concept and Decision Tree Visualization in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Backtracking Path Exploration

What is the printed output of the following Java backtracking code that explores all subsets of {1, 2}?

DSA Java

import java.util.*;

public class BacktrackDemo {
    static void backtrack(List<Integer> nums, int start, List<Integer> path) {
        System.out.println(path);
        for (int i = start; i < nums.size(); i++) {
            path.add(nums.get(i));
            backtrack(nums, i + 1, path);
            path.remove(path.size() - 1);
        }
    }

    public static void main(String[] args) {
        List<Integer> nums = Arrays.asList(1, 2);
        backtrack(nums, 0, new ArrayList<>());
    }
}

A

[]
[1]
[1, 2]
[2]

B

[1]
[1, 2]
[2]
[]

C

[]
[2]
[1]
[1, 2]

D

[1, 2]
[1]
[2]
[]

💡 Hint

Trace the recursive calls and note when the current path is printed.

The code prints the current path at each recursive call before exploring further elements. It starts with an empty list, then adds 1, then adds 2, backtracks, and finally adds 2 alone.

🧠 Conceptual

intermediate

Number of Nodes in Backtracking Decision Tree

For a backtracking algorithm that generates all subsets of a set with 3 elements, how many nodes are there in the decision tree including the root and all leaves?

A 16

B 7

C 8

D 15

💡 Hint

Each element can be either included or excluded, forming a binary tree.

For n elements, the decision tree has 2^n leaves and total nodes equal to 2^(n+1) - 1. For n=3, total nodes = 2^4 - 1 = 15.

🔧 Debug

advanced

Identify the Error in Backtracking Code

What error will the following Java code produce when run?

DSA Java

import java.util.*;

public class BacktrackBug {
    static void backtrack(List<Integer> nums, int start, List<Integer> path) {
        if (start == nums.size()) {
            System.out.println(path);
            return;
        }
        path.add(nums.get(start));
        backtrack(nums, start + 1, path);
        path.remove(path.size() - 1);
        backtrack(nums, start + 1, path);
    }

    public static void main(String[] args) {
        List<Integer> nums = Arrays.asList(1, 2, 3);
        backtrack(nums, 0, new ArrayList<>());
    }
}

A No output, infinite recursion

B IndexOutOfBoundsException

C NullPointerException

D Correct output with all subsets printed

💡 Hint

Check the index used in path.remove().

The code removes element at index 'start' from path, but path size changes during recursion. This causes IndexOutOfBoundsException when start is greater than path size.

🚀 Application

advanced

Backtracking to Generate Permutations

Which output corresponds to the permutations generated by the following Java backtracking code for input [1, 2]?

DSA Java

import java.util.*;

public class PermutationBacktrack {
    static void backtrack(List<Integer> nums, List<Integer> path, boolean[] used) {
        if (path.size() == nums.size()) {
            System.out.println(path);
            return;
        }
        for (int i = 0; i < nums.size(); i++) {
            if (used[i]) continue;
            used[i] = true;
            path.add(nums.get(i));
            backtrack(nums, path, used);
            path.remove(path.size() - 1);
            used[i] = false;
        }
    }

    public static void main(String[] args) {
        List<Integer> nums = Arrays.asList(1, 2);
        backtrack(nums, new ArrayList<>(), new boolean[nums.size()]);
    }
}

A

[1]
[2]

B

[2, 1]
[1, 2]

C

[1, 2]
[2, 1]

D

[1, 2]
[1, 2]

💡 Hint

Permutations list all orderings of elements.

The code generates all permutations of [1, 2], which are [1, 2] and [2, 1].

🧠 Conceptual

expert

Backtracking Tree Pruning Effect

In a backtracking algorithm solving the N-Queens problem, pruning branches early reduces the number of nodes explored. If pruning cuts off half the branches at each level for N=4, how many nodes are explored approximately compared to the full 2^(N^2) search space?

A Approximately 2^(4) nodes

B Approximately 2^(8) nodes

C Approximately 2^(16) nodes

D Approximately 2^(2) nodes

💡 Hint

N=4 means 4 queens on 4x4 board; full search space is 2^(16). Pruning halves branches each level.

Full search space is 2^(N^2) = 2^16 = 65536 nodes. Pruning halves branches at each of N=4 levels, so nodes ≈ 2^(N^2) / 2^N = 2^(16-4) = 2^12. But pruning at each queen placement level reduces more, approximated here as 2^(4).

Practice

1. What is the main idea behind backtracking in algorithms?

easy

A. Try all possible options and undo choices when they lead to dead ends

B. Sort the input data before processing

C. Use a queue to process elements in order

D. Divide the problem into smaller independent parts

Solution

1. Step 1: Understand backtracking approach

   Backtracking tries all possible choices step-by-step and goes back if a choice fails.

2. Step 2: Compare options with backtracking definition

   Only Try all possible options and undo choices when they lead to dead ends describes trying options and undoing wrong choices, which is backtracking.

3. Final Answer:

   Try all possible options and undo choices when they lead to dead ends -> Option A

4. Quick Check:

   Backtracking = Try and undo choices [OK]

Hint: Backtracking means try, fail, and undo to try again [OK]

Common Mistakes:

• Confusing backtracking with sorting or dividing problems
• Thinking backtracking uses queues or simple loops
• Believing backtracking never undoes choices

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

easy

A. backtrack() void { ... }

B. void backtrack(int step) { ... }

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

D. function backtrack(int step) { ... }

Solution

1. Step 1: Recall Java method syntax

   Java methods start with return type, then name, then parameters in parentheses.

2. Step 2: Check each option

   void backtrack(int step) { ... } uses correct Java syntax: return type void, method name, parameter list. A: backtrack() void { ... } has wrong order, B: backtrack(int step) { ... } misses return type, D uses 'function' keyword which is not Java.

3. Final Answer:

   void backtrack(int step) { ... } -> Option B

4. Quick Check:

   Java method syntax = void backtrack(int step) { ... } [OK]

Hint: Java methods start with return type, then name, then parameters [OK]

Common Mistakes:

• Using 'function' keyword like JavaScript
• Placing return type after method name
• Omitting the return type

3. What will be the output of the following Java backtracking code snippet?

public class Test {
  static void backtrack(int step) {
    if (step == 3) {
      System.out.print(step + " ");
      return;
    }
    System.out.print(step + " ");
    backtrack(step + 1);
    System.out.print(step + " ");
  }
  public static void main(String[] args) {
    backtrack(1);
  }
}

medium

A. 1 2 1

B. 1 2 3

C. 3 2 1

D. 1 2 3 2 1

Solution

1. Step 1: Trace forward calls and prints

   backtrack(1) prints '1 ', calls backtrack(2). backtrack(2) prints '2 ', calls backtrack(3). backtrack(3) prints '3 ' and returns.

2. Step 2: Trace backward prints after recursion

   After backtrack(3) returns, backtrack(2) prints '2 ', then backtrack(1) prints '1 ' after its recursive call.

3. Final Answer:

   1 2 3 2 1 -> Option D

4. Quick Check:

   Print before and after recursion = 1 2 3 2 1 [OK]

Hint: Print before and after recursion shows mirrored output [OK]

Common Mistakes:

• Ignoring prints after recursive call
• Assuming only forward prints happen
• Confusing base case output

4. Identify the error in this backtracking code snippet:

void backtrack(int step) {
  if (step > 3) return;
  System.out.print(step + " ");
  backtrack(step + 1);
}

medium

A. Missing base case to stop recursion

B. No print statement after recursion to backtrack

C. No error, code works correctly

D. Base case condition is incorrect, should be step == 3

Solution

1. Step 1: Analyze base case condition

   The base case stops recursion when step > 3, so calls happen for step=1,2,3 then stop.

2. Step 2: Check print and recursion flow

   Print happens before recursion, so output is '1 2 3 '. No error in stopping or printing.

3. Final Answer:

   No error, code works correctly -> Option C

4. Quick Check:

   Base case and print correct = No error [OK]

Hint: Check base case carefully to confirm recursion stops [OK]

Common Mistakes:

• Thinking base case must be step == 3
• Expecting print after recursion for backtracking
• Assuming missing braces cause error

5. Given a decision tree for backtracking with choices A and B at each step up to 2 steps, how many total paths (leaf nodes) will the tree have?

medium

A. 4

B. 3

C. 2

D. 8

Solution

1. Step 1: Understand decision tree branching

   Each step has 2 choices (A or B), so the tree branches twice per step.

2. Step 2: Calculate total leaf nodes for 2 steps

   Number of leaf nodes = 2 choices ^ 2 steps = 2 * 2 = 4 total paths.

3. Final Answer:

   4 -> Option A

4. Quick Check:

   2 choices ^ 2 steps = 4 [OK]

Hint: Total paths = choices^steps in decision tree [OK]

Common Mistakes:

• Adding instead of multiplying choices
• Confusing steps with choices
• Forgetting to count all leaf nodes