Backtracking Explained: How to Solve Problems by Undoing Bad Choices

import java.util.ArrayList;
import java.util.List;

/**
 * Generates all subsets (the power set) of a given array of integers.
 * This is the simplest real showcase of the backtracking pattern:
 * choose -> explore -> unchoose.
 */
public class SubsetGenerator {

    public static void main(String[] args) {
        int[] numbers = {1, 2, 3};
        List<List<Integer>> allSubsets = new ArrayList<>();

        generateSubsets(numbers, 0, new ArrayList<>(), allSubsets);

        System.out.println("All subsets of " + java.util.Arrays.toString(numbers) + ":");
        for (List<Integer> subset : allSubsets) {
            System.out.println(subset);
        }
        System.out.println("Total subsets: " + allSubsets.size());
    }

    /**
     * @param numbers       The input array we're building subsets from
     * @param startIndex    The index we're currently deciding to include or skip
     * @param currentSubset The subset we're building up incrementally
     * @param results       Accumulator — stores every complete subset we find
     */
    private static void generateSubsets(
            int[] numbers,
            int startIndex,
            List<Integer> currentSubset,
            List<List<Integer>> results) {

        // BASE CASE: record a snapshot of the current subset as a valid result.
        // We do this at EVERY level, not just leaves — every partial build is a valid subset.
        results.add(new ArrayList<>(currentSubset));

        // EXPLORE: try adding each remaining number to the current subset
        for (int i = startIndex; i < numbers.length; i++) {

            // CHOOSE: add numbers[i] to the current subset
            currentSubset.add(numbers[i]);

            // RECURSE: explore all subsets that start with what we've chosen so far
            // We pass i+1 so we never re-use the same element
            generateSubsets(numbers, i + 1, currentSubset, results);

            // UNCHOOSE: remove numbers[i] — restore state for the next iteration
            // Without this line, each recursive call would pollute the next one
            currentSubset.remove(currentSubset.size() - 1);
        }
    }
}

import java.util.ArrayList;
import java.util.List;

/**
 * Solves the N-Queens problem using backtracking with pruning.
 * Places N queens on an N x N board so no two queens threaten each other.
 */
public class NQueensSolver {

    public static void main(String[] args) {
        int boardSize = 4;
        List<int[]> solutions = new ArrayList<>();

        // queenInRow[col] = the row where we placed the queen in column 'col'
        int[] queenInRow = new int[boardSize];

        solveNQueens(boardSize, 0, queenInRow, solutions);

        System.out.println("Solutions for " + boardSize + "-Queens:\n");
        for (int solutionNumber = 0; solutionNumber < solutions.size(); solutionNumber++) {
            System.out.println("Solution " + (solutionNumber + 1) + ":");
            printBoard(solutions.get(solutionNumber), boardSize);
        }
        System.out.println("Total solutions: " + solutions.size());
    }

    /**
     * Tries to place a queen in each row of the current column.
     *
     * @param boardSize   Size of the board (N)
     * @param currentCol  The column we're currently trying to fill
     * @param queenInRow  Records which row holds the queen for each column
     * @param solutions   Accumulates all valid complete board configurations
     */
    private static void solveNQueens(
            int boardSize,
            int currentCol,
            int[] queenInRow,
            List<int[]> solutions) {

        // BASE CASE: we've successfully placed queens in all columns
        if (currentCol == boardSize) {
            solutions.add(queenInRow.clone()); // snapshot — not a reference!
            return;
        }

        // Try placing a queen in each row of the current column
        for (int candidateRow = 0; candidateRow < boardSize; candidateRow++) {

            // PRUNING: skip this row if it conflicts with any previously placed queen
            if (isPlacementSafe(queenInRow, currentCol, candidateRow)) {

                // CHOOSE: place the queen
                queenInRow[currentCol] = candidateRow;

                // RECURSE: move on to the next column
                solveNQueens(boardSize, currentCol + 1, queenInRow, solutions);

                // UNCHOOSE: no explicit reset needed here because we overwrite
                // queenInRow[currentCol] on the next iteration anyway.
                // For clarity in more complex problems, you'd zero it out here.
            }
            // If not safe, we skip the entire subtree — this is the pruning step
        }
    }

    /**
     * Checks whether placing a queen at (candidateRow, currentCol) conflicts
     * with any queen already placed in columns 0..currentCol-1.
     */
    private static boolean isPlacementSafe(
            int[] queenInRow,
            int currentCol,
            int candidateRow) {

        for (int placedCol = 0; placedCol < currentCol; placedCol++) {
            int placedRow = queenInRow[placedCol];

            // Same row? Conflict.
            boolean sameRow = (placedRow == candidateRow);

            // Same diagonal? The row difference equals the column difference.
            int rowDiff = Math.abs(placedRow - candidateRow);
            int colDiff = Math.abs(placedCol - currentCol);
            boolean sameDiagonal = (rowDiff == colDiff);

            if (sameRow || sameDiagonal) {
                return false; // Prune: this placement is immediately illegal
            }
        }
        return true; // No conflicts found — safe to place
    }

    /** Renders a board configuration as a grid of Q (queen) and . (empty). */
    private static void printBoard(int[] queenInRow, int boardSize) {
        for (int row = 0; row < boardSize; row++) {
            StringBuilder line = new StringBuilder();
            for (int col = 0; col < boardSize; col++) {
                line.append(queenInRow[col] == row ? " Q " : " . ");
            }
            System.out.println(line);
        }
        System.out.println();
    }
}

import java.util.ArrayList;
import java.util.List;

/**
 * Generates ALL permutations of a string using backtracking.
 * Demonstrates using a boolean array to track 'visited' state,
 * which must be carefully restored on unchoose.
 */
public class PermutationGenerator {

    public static void main(String[] args) {
        String input = "ABC";
        List<String> permutations = new ArrayList<>();

        boolean[] characterUsed = new boolean[input.length()];

        buildPermutations(input.toCharArray(), characterUsed, new StringBuilder(), permutations);

        System.out.println("All permutations of \"" + input + "\":");
        permutations.forEach(System.out::println);
        System.out.println("Total: " + permutations.size() + " (expected: " + factorial(input.length()) + ")");
    }

    private static void buildPermutations(
            char[] characters,
            boolean[] characterUsed,
            StringBuilder currentPermutation,
            List<String> results) {

        // BASE CASE: we've used every character — record this permutation
        if (currentPermutation.length() == characters.length) {
            results.add(currentPermutation.toString());
            return;
        }

        for (int i = 0; i < characters.length; i++) {

            // PRUNING: skip characters already in the current permutation
            if (characterUsed[i]) {
                continue;
            }

            // CHOOSE: use this character and mark it as taken
            characterUsed[i] = true;
            currentPermutation.append(characters[i]);

            // RECURSE: fill the next position
            buildPermutations(characters, characterUsed, currentPermutation, results);

            // UNCHOOSE: remove the character and free it for other permutations
            // Forgetting either of these two lines is the #1 backtracking bug
            currentPermutation.deleteCharAt(currentPermutation.length() - 1);
            characterUsed[i] = false;
        }
    }

    private static int factorial(int n) {
        return (n <= 1) ? 1 : n * factorial(n - 1);
    }
}