Backtracking is essentially a specialized version of recursion where you're searching for a solution by trying one path, realizing it's a dead end, and then "undoing" your last move to try a different one. If you've ever solved a maze by putting your hand on the wall and turning back when you hit a corner, you've performed a manual backtracking algorithm.

The hardest part for most developers isn't the recursion itself—it's managing the state. I often see learners treat backtracking like a standard depth-first search, forgetting that they have to leave the environment exactly how they found it before the function returns. Let's look at a common mess-up.

The Permutation State Leak

Suppose you're trying to generate all possible permutations of a string. You might write something like this. It looks logically sound at first glance: you pick a character, mark it as used, and move to the next position.

public void findPermutations(String str, StringBuilder current, boolean[] used) {
    if (current.length() == str.length()) {
        System.out.println(current.toString());
        return;
    }

    for (int i = 0; i < str.length(); i++) {
        if (!used[i]) {
            used[i] = true;
            current.append(str.charAt(i));
            findPermutations(str, current, used);
            // I'm missing something here...
        }
    }
}

If you run this with the string "ABC", you won't get six permutations. You'll get one correct one ("ABC"), and then the code will either crash or produce gibberish. Why? Because current and used are passed by reference. When the recursion hits the base case and returns, the StringBuilder still contains "ABC" and the used array is still all true. The previous calls in the stack have no idea the state was modified, so they can't try the next available character.

Restoring State After Recursion

To fix this, you need to implement the "Choose, Explore, Unchoose" pattern. This is the heartbeat of every backtracking algorithm. You make a choice, you dive deep into that choice, and then you explicitly revert that choice before the method finishes.

public void findPermutations(String str, StringBuilder current, boolean[] used) {
    if (current.length() == str.length()) {
        System.out.println(current.toString());
        return;
    }

    for (int i = 0; i < str.length(); i++) {
        if (!used[i]) {
            // 1. CHOOSE
            used[i] = true;
            current.append(str.charAt(i));

            // 2. EXPLORE
            findPermutations(str, current, used);

            // 3. UNCHOOSE (The magic step)
            used[i] = false;
            current.deleteCharAt(current.length() - 1);
        }
    }
}

By deleting the last character and resetting the used flag, you're cleaning up after yourself. When the loop moves to i + 1, it's as if the previous attempt never happened. I always tell people to think of it like a transactional database: if the "transaction" (the recursive call) finishes, you must roll back the changes to the shared state so the next transaction starts fresh.

Pruning the Search Tree

In more complex problems—like the N-Queens problem or Sudoku solvers—backtracking becomes powerful when you add "pruning." Pruning is just a fancy way of saying "stop searching this path as soon as you know it's impossible."

Instead of waiting until you reach the base case to see if a solution is valid, you check the constraints before making the recursive call. If placing a queen at (row, col) violates a rule, you don't call findPermutations for that branch at all. This turns an exponential nightmare into something manageable. If you find your backtracking code is taking forever to run, you're likely exploring paths that could have been pruned five levels higher up the tree.

📋 Practical Task

Build a Valid Parentheses Generator

Your task is to implement a backtracking algorithm that generates all combinations of well-formed parentheses. Given an integer n representing the number of pairs, you need to return a list of all possible strings.

Constraints:

• You cannot add a closing parenthesis ')' unless there is a matching open parenthesis '(' already in the string.
• You cannot add more than n opening parentheses.

Requirements:

1. Implement a method public List<String> generateParenthesis(int n).
2. Use a StringBuilder to maintain the current string state.
3. Ensure you are using the "Choose, Explore, Unchoose" pattern to manage the StringBuilder.
4. Verify your logic: For n = 3, your code should produce ["((()))","(()())","(())()","()(())","()()()"].