Backtracking is a powerful algorithmic technique used for solving optimization problems, puzzles, and search problems, especially when exploring all possible solutions or configurations is required. In backtracking, you incrementally build a solution by trying out each possible option, and if a particular option leads to an invalid solution, you backtrack and try the next option.

In this blog, we'll dive into what backtracking is, how it works, and explore common problems solved using backtracking, all while providing Java code examples for clarity.

📚 What is Backtracking?

Backtracking is a method of solving problems where the solution involves searching through all possible candidates to find one (or more) that satisfies a given condition. When an intermediate solution seems invalid or doesn’t lead to a solution, we backtrack to the previous step, discard the current path, and try a new one.

Backtracking is often used for solving combinatorial problems, constraint satisfaction problems, and search problems, where:

  • A solution is constructed incrementally.
  • You abandon a solution as soon as you determine that it can't be extended to a valid solution.

🚀 How Backtracking Works

Backtracking works by using a recursive approach to explore all possible solutions. Here's the general process:

  1. Choose: Choose an option from a set of possible options.
  2. Explore: Explore the solution recursively by moving forward with the current choice.
  3. Unchoose: If the current path leads to a valid solution, the algorithm proceeds; otherwise, it backtracks by undoing the last choice and tries the next possible option.

This cycle continues until all solutions are found or a solution is discovered.

⚙️ Template of Backtracking 

void backtrack(Parameters...) {
    // ✅ 1. Base case: when to stop
    if (isSolution(...)) {
        result.add(new ArrayList<>(current));
        return;
    }

    // 🔁 2. Iterate over choices
    for (int i = start; i < end; i++) {

        // 🚫 3. Pruning (skip invalid choices)
        if (isInvalid(i)) continue;

        // ✅ 4. Make a choice
        current.add(choice[i]);
        markUsed(i);

        // 🔁 5. Explore (go deeper)
        backtrack(updatedParameters...);

        // ↩️ 6. Undo the choice (backtrack)
        current.remove(current.size() - 1);
        unmarkUsed(i);
    }
}

💡 Must-Know Backtracking Problems (with Java Code)

1. Generate All Subsets (Power Set) 

void subsets(int[] nums, int index, List<Integer> current, List<List<Integer>> result) {
    result.add(new ArrayList<>(current));
    for (int i = index; i < nums.length; i++) {
        current.add(nums[i]);
        subsets(nums, i + 1, current, result);
        current.remove(current.size() - 1);
    }
}

2. Permutations of Distinct Integers 

void permute(int[] nums, List<Integer> current, boolean[] used, List<List<Integer>> result) {
    if (current.size() == nums.length) {
        result.add(new ArrayList<>(current));
        return;
    }
    for (int i = 0; i < nums.length; i++) {
        if (used[i]) continue;
        used[i] = true;
        current.add(nums[i]);
        permute(nums, current, used, result);
        current.remove(current.size() - 1);
        used[i] = false;
    }
}

3. Combination Sum 

void combinationSum(int[] candidates, int target, int start, List<Integer> current, List<List<Integer>> result) {
    if (target == 0) {
        result.add(new ArrayList<>(current));
        return;
    }
    for (int i = start; i < candidates.length; i++) {
        if (candidates[i] > target) continue;
        current.add(candidates[i]);
        combinationSum(candidates, target - candidates[i], i, current, result);
        current.remove(current.size() - 1);
    }
}

🛠️ Common Backtracking Problems

Let's go over some classic problems that are commonly solved using backtracking.

1. N-Queens Problem

The N-Queens problem is a classic backtracking problem where the task is to place n queens on an n x n chessboard such that no two queens threaten each other. Queens can attack horizontally, vertically, and diagonally.

Code Example (N-Queens Problem): 

public class NQueens {
    private static final int N = 4; // Size of the board

    // Function to print the board
    public static void printSolution(int[][] board) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                System.out.print(board[i][j] + " ");
            }
            System.out.println();
        }
    }

    // Function to check if a queen can be placed at board[row][col]
    public static boolean isSafe(int[][] board, int row, int col) {
        // Check for other queens in the same column
        for (int i = 0; i < row; i++) {
            if (board[i][col] == 1) {
                return false;
            }
        }

        // Check upper left diagonal
        for (int i = row, j = col; i >= 0 && j >= 0; i--, j--) {
            if (board[i][j] == 1) {
                return false;
            }
        }

        // Check upper right diagonal
        for (int i = row, j = col; i >= 0 && j < N; i--, j++) {
            if (board[i][j] == 1) {
                return false;
            }
        }

        return true;
    }

    // Function to solve N-Queens problem using backtracking
    public static boolean solveNQueens(int[][] board, int row) {
        if (row == N) {
            printSolution(board);
            return true;
        }

        for (int col = 0; col < N; col++) {
            if (isSafe(board, row, col)) {
                board[row][col] = 1; // Place queen
                if (solveNQueens(board, row + 1)) {
                    return true;
                }
                board[row][col] = 0; // Backtrack
            }
        }

        return false; // No solution
    }

    public static void main(String[] args) {
        int[][] board = new int[N][N];
        if (!solveNQueens(board, 0)) {
            System.out.println("Solution does not exist");
        }
    }
}

Output (for N = 4): 

1 0 0 0 
0 0 1 0 
0 1 0 0 
0 0 0 1

In this solution:

  • We use a recursive function to place queens one by one in each row.
  • For each queen, we check if it is safe to place in the current column by checking the column, upper left diagonal, and upper right diagonal.
  • If placing the queen leads to a valid solution, we proceed to the next row. If not, we backtrack and remove the queen.

2. Subset Sum Problem

Given a set of numbers, the subset sum problem asks whether there is a subset of numbers that sums up to a given target value.

Code Example (Subset Sum Problem): 

import java.util.*;

public class SubsetSum {
    // Function to check if a subset sum exists
    public static boolean isSubsetSum(int[] arr, int n, int target) {
        if (target == 0) {
            return true; // If target sum is 0, return true
        }
        if (n == 0) {
            return false; // No elements left
        }

        // If last element is greater than target, ignore it
        if (arr[n - 1] > target) {
            return isSubsetSum(arr, n - 1, target);
        }

        // Include the last element or exclude it
        return isSubsetSum(arr, n - 1, target) || isSubsetSum(arr, n - 1, target - arr[n - 1]);
    }

    public static void main(String[] args) {
        int[] arr = {3, 34, 4, 12, 5, 2};
        int target = 9;
        int n = arr.length;

        if (isSubsetSum(arr, n, target)) {
            System.out.println("Subset with given sum exists");
        } else {
            System.out.println("No subset with given sum");
        }
    }
}

Output: 

Subset with given sum exists

In this solution:

  • We recursively decide whether to include each element in the subset or not.
  • If including the element results in the sum being equal to the target, we return true.

3. Permutations

In the Permutations problem, we need to generate all the possible permutations of a given set of elements.

Code Example (Permutations): 

import java.util.*;

public class Permutations {
    // Function to generate all permutations
    public static void generatePermutations(int[] nums, int start, List<List<Integer>> result) {
        if (start == nums.length) {
            List<Integer> perm = new ArrayList<>();
            for (int num : nums) {
                perm.add(num);
            }
            result.add(perm);
            return;
        }

        for (int i = start; i < nums.length; i++) {
            // Swap current element with the start element
            swap(nums, start, i);
            // Recurse with next index
            generatePermutations(nums, start + 1, result);
            // Backtrack (restore the array)
            swap(nums, start, i);
        }
    }

    // Swap two elements in an array
    private static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        List<List<Integer>> result = new ArrayList<>();
        generatePermutations(nums, 0, result);
        System.out.println(result);
    }
}

Output: 

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

In this solution:

  • We recursively swap elements to generate all possible permutations.
  • After swapping, we recurse on the next index until all elements are visited.
  • If we reach the end of the array, we add the current permutation to the result.

🧠 Time and Space Complexity

Time Complexity:

  • N-Queens: O(N!), because there are N! possible arrangements of queens on the board.
  • Subset Sum: O(2^N), since we explore every subset of the set.
  • Permutations: O(N!), as there are N! permutations of an array of N elements.

Space Complexity:

  • N-Queens: O(N^2), due to the storage of the board.
  • Subset Sum: O(N), for recursion stack.
  • Permutations: O(N!), for storing the permutations.

🎯 Applications of Backtracking

  1. Solving Puzzles: Problems like Sudoku, N-Queens, and Crossword puzzles.
  2. Combination and Permutation Problems: Finding all subsets or combinations of a set of elements.
  3. Constraint Satisfaction Problems: Problems like the 8-Queens problem or coloring graphs.
  4. Pathfinding in a Maze: Exploring all possible paths from a start point to an endpoint.

📝 Conclusion

Backtracking is a versatile and powerful algorithmic technique that helps in solving problems involving multiple possibilities or configurations. Whether you're solving puzzles, optimization problems, or generating permutations and combinations, backtracking offers a clean and efficient way to explore all possibilities while pruning invalid solutions early.