Recursion and Backtracking in Java

When you solve a maze on paper, you follow a path until you hit a wall. Then you go back to the last place where you had a choice and try a different way. You never start again from the beginning, and you never try a path you have already ruled out. That habit of trying, hitting a dead end, and stepping back is called backtracking. Written as recursive Java code, it solves puzzles such as arranging students in every possible order, choosing subjects within a budget, or placing queens on a chessboard. In this lesson, you will review the recursion rules backtracking depends on, learn the choose, explore, unchoose pattern, and use it on three classic problems.

Recursion in One Minute

A recursive method is a method that calls itself on a smaller version of the same problem. Every recursive method needs:

1. A base case: a version so small the answer is known, which stops the recursion.
2. A recursive case: a step that makes the problem smaller and calls the method again.

The details, including the call stack and StackOverflowError, are in "Recursion in Java" and "Recursion vs Iteration".

What Is Backtracking?

Backtracking in Java is a recursive technique that is used to explore all possible solutions by building a candidate one choice at a time, and undoing the last choice (backtracking) as soon as it can't lead to a valid solution, or once it has been fully explored.

Every backtracking method follows the same three steps:

Example 1: All Orders (Permutations)

Let's see an example that lists every order in which three students can stand in a line, printing the decision tree as it goes.

import java.util.ArrayList;
import java.util.List;
 
public class LineUp {
    static void permute(List<String> chosen, List<String> left, int depth) {
        if (left.isEmpty()) {
            System.out.println("  ".repeat(depth) + "=> " + chosen);
            return;
        }
        for (int i = 0; i < left.size(); i++) {
            String pick = left.remove(i);            // choose
            chosen.add(pick);
            System.out.println("  ".repeat(depth) + "pick " + pick);
            permute(chosen, left, depth + 1);        // explore
            chosen.remove(chosen.size() - 1);        // unchoose
            left.add(i, pick);
        }
    }
 
    public static void main(String[] args) {
        List<String> students = new ArrayList<>(
                List.of("Navika", "Srihitha", "Advitha"));
        permute(new ArrayList<>(), students, 0);
    }
}

pick Navika
  pick Srihitha
    pick Advitha
      => [Navika, Srihitha, Advitha]
  pick Advitha
    pick Srihitha
      => [Navika, Advitha, Srihitha]
pick Srihitha
  pick Navika
    pick Advitha
      => [Srihitha, Navika, Advitha]
  pick Advitha
    pick Navika
      => [Srihitha, Advitha, Navika]
pick Advitha
  pick Navika
    pick Srihitha
      => [Advitha, Navika, Srihitha]
  pick Srihitha
    pick Navika
      => [Advitha, Srihitha, Navika]

Explanation:

1. At each level, the loop tries every student still left as the next in line.
2. Choose: the student moves from left to chosen. Explore: the recursive call fills the remaining places. Unchoose: the student goes back to left at the same position, so the next loop iteration starts from the same state.
3. When left is empty, a complete order has been built (the base case), and it is printed with =>.
4. The indentation shows the decision tree: 3 choices, then 2, then 1, giving 3 × 2 × 1 = 6 orders.

Example 2: Subjects Within a Budget (Subsets)

For subsets, each item has two choices: take it or skip it. Backtracking can also prune: stop exploring a branch as soon as it breaks a rule.

import java.util.ArrayList;
import java.util.List;
 
public class Electives {
    static final String[] NAMES = {"Robotics", "Music", "Chess", "Art"};
    static final int[] FEES = {3000, 1500, 1000, 2000};
 
    static void choose(int i, int budgetLeft, List<String> picked) {
        if (i == NAMES.length) {
            System.out.println(picked + " leaves " + budgetLeft);
            return;
        }
        if (FEES[i] <= budgetLeft) {                     // prune: affordable?
            picked.add(NAMES[i]);                        // choose: take it
            choose(i + 1, budgetLeft - FEES[i], picked); // explore
            picked.remove(picked.size() - 1);            // unchoose
        }
        choose(i + 1, budgetLeft, picked);               // or skip it
    }
 
    public static void main(String[] args) {
        choose(0, 4000, new ArrayList<>());
    }
}

[Robotics, Chess] leaves 0
[Robotics] leaves 1000
[Music, Chess] leaves 1500
[Music, Art] leaves 500
[Music] leaves 2500
[Chess, Art] leaves 1000
[Chess] leaves 3000
[Art] leaves 2000
[] leaves 4000

Explanation: with 4 electives there are 2⁴ = 16 possible subsets, but only the ones that fit the ₹4,000 budget are printed. The check FEES[i] <= budgetLeft prunes every branch that would go over budget before exploring it, so the method never wastes time on combinations that can't work.

Example 3: The 4-Queens Puzzle

Place 4 queens on a 4 × 4 chessboard so that no two attack each other (no shared row, column or diagonal). Place one queen per row, and backtrack whenever a square is attacked.

public class Queens {
    static final int N = 4;
    static int[] col = new int[N];       // col[row] = column of its queen
    static int solutions = 0;
 
    static boolean safe(int row, int c) {
        for (int r = 0; r < row; r++) {
            if (col[r] == c || Math.abs(col[r] - c) == row - r) {
                return false;            // same column or same diagonal
            }
        }
        return true;
    }
 
    static void place(int row) {
        if (row == N) {
            solutions++;
            for (int r = 0; r < N; r++) {
                System.out.println(". ".repeat(col[r]) + "Q "
                        + ". ".repeat(N - col[r] - 1));
            }
            System.out.println();
            return;
        }
        for (int c = 0; c < N; c++) {
            if (safe(row, c)) {
                col[row] = c;            // choose
                place(row + 1);          // explore
            }                            // unchoose: next c overwrites col[row]
        }
    }
 
    public static void main(String[] args) {
        place(0);
        System.out.println(solutions + " solutions");
    }
}

. Q . .
. . . Q
Q . . .
. . Q .
 
. . Q .
Q . . .
. . . Q
. Q . .
 
2 solutions

Explanation: row by row, the method tries each column and keeps only safe ones. When no column in a row is safe, the loop simply ends, and the method returns to the previous row, which tries its next column: that return is the backtrack. Here the "unchoose" step is automatic, because the next choice overwrites col[row].

Complexity

Backtracking explores a tree of choices, so it is usually exponential:

Pruning is what makes backtracking practical: the earlier a branch is rejected, the more of the tree is skipped.

Interview Corner

Practice

1. Easy: Remove the line left.add(i, pick); from LineUp.java and run it. Explain what goes wrong.
2. Harder: Change Queens.java to N = 6 and print only the number of solutions (answer: 4). Then try N = 8 (answer: 92).

Key Takeaways