Backtracking N Queens, Subset Sum Problems

What is Backtracking?

Backtracking is a general problem-solving technique used for searching all possible solutions while pruning choices that cannot lead to a valid answer. It builds a solution step by step and abandons a partial solution as soon as it becomes invalid or unpromising.

You can think of backtracking as a depth-first search on a decision tree. Each level of the tree represents a choice. When one choice fails, we undo it and try the next possibility.

Core Idea

This is often called the choose-explore-unchoose pattern.

Choose: make one possible decision.
Explore: recursively continue with that decision.
Unchoose: undo the decision and try another one.

Why Backtracking Works

Many combinational problems can be viewed as building a partial answer one step at a time. If at any point the partial answer already breaks the problem's rules, then there is no need to explore deeper. That branch can be cut immediately. This pruning is what makes backtracking more powerful than naive brute force.

Backtracking vs Brute Force vs DFS

Technique	Main Idea	Key Difference
Brute force	Try every possibility	No pruning
DFS	Explore deeply before backtracking	Traversal strategy, not always constraint-based
Backtracking	DFS + pruning invalid branches	Stops early when a branch cannot succeed

When to Use Backtracking

When the problem asks for all solutions or whether any valid solution exists.
When the solution is built incrementally.
When constraints allow us to reject bad partial solutions early.
In puzzles, search problems, arrangement problems, and constraint satisfaction problems.

Common Backtracking Problems

Problem	Typical Choice	Constraint
N-Queens	Place a queen in a row	No same column or diagonal
Subset Sum	Include or exclude an element	Target sum must be achievable
Rat in a Maze	Move to a neighboring cell	Stay inside open, unvisited cells
Sudoku	Place a digit in a cell	Row, column, and box rules
Graph Coloring	Assign a color to a vertex	Adjacent vertices cannot share a color
Permutations / Combinations	Pick next element	Avoid duplicates or repeated use

General Backtracking Template

Most backtracking solutions follow the same recursive structure:

General Backtracking Template - Java Example

void backtrack(State state) {
    if (isSolution(state)) {
        record(state);
        return;
    }

    for (Choice choice : choices(state)) {
        if (!isValid(state, choice)) continue;  // prune

        apply(state, choice);    // CHOOSE
        backtrack(state);        // EXPLORE
        undo(state, choice);     // UNCHOOSE
    }
}

1. N-Queens Problem

The N-Queens problem asks us to place N queens on an N x N chessboard so that no two queens attack each other. Since queens attack horizontally, vertically, and diagonally, each placement must be checked carefully.

The usual backtracking idea is to place exactly one queen in each row. For every row, try every column. If a position is safe, place the queen and move to the next row. Otherwise skip that position.

N-Queens Problem

public class NQueens {

    static int n;
    static int[] board;  // board[row] = column of queen in that row
    static int solutions = 0;

    static boolean isSafe(int row, int col) {
        for (int r = 0; r < row; r++) {
            if (board[r] == col) return false;  // same column
            if (Math.abs(board[r] - col) == Math.abs(r - row)) return false;  // diagonal
        }
        return true;
    }

    static void solve(int row) {
        if (row == n) {
            solutions++;
            printBoard();
            return;
        }

        for (int col = 0; col < n; col++) {
            if (isSafe(row, col)) {
                board[row] = col;    // CHOOSE
                solve(row + 1);      // EXPLORE
                board[row] = -1;     // UNCHOOSE
            }
        }
    }

    static void printBoard() {
        System.out.println("Solution " + solutions + ":");
        for (int r = 0; r < n; r++) {
            for (int c = 0; c < n; c++) {
                System.out.print(board[r] == c ? "Q " : ". ");
            }
            System.out.println();
        }
        System.out.println();
    }

    public static void main(String[] args) {
        n = 4;
        board = new int[n];
        java.util.Arrays.fill(board, -1);
        solve(0);
        System.out.println("Total solutions for " + n + "-Queens: " + solutions);
    }
}

2. Subset Sum Problem

In subset sum, we decide for each element whether to include it or exclude it. That naturally gives a binary decision tree. Backtracking becomes useful because if the current sum already exceeds the target, we may prune that branch in suitable cases.

The pruning below assumes non-negative numbers. If negative numbers are allowed, the `currentSum > target` pruning rule is not always safe.

Subset Sum Problem

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

public class SubsetSum {

    // Assumes all numbers are non-negative
    static void findSubsets(int[] arr, int target, int idx,
                            int currentSum, List<Integer> current) {
        if (currentSum == target) {
            System.out.println("Found: " + current);
            return;
        }

        if (idx == arr.length || currentSum > target) return;  // prune

        // CHOOSE: include arr[idx]
        current.add(arr[idx]);
        findSubsets(arr, target, idx + 1, currentSum + arr[idx], current);

        // UNCHOOSE: exclude arr[idx]
        current.remove(current.size() - 1);
        findSubsets(arr, target, idx + 1, currentSum, current);
    }

    public static void main(String[] args) {
        int[] arr = {3, 1, 4, 2, 5};
        int target = 6;
        System.out.println("Subsets summing to " + target + ":");
        findSubsets(arr, target, 0, 0, new ArrayList<>());
        // Possible outputs: [3, 1, 2], [1, 5], [4, 2]
    }
}

3. Rat in a Maze

In the Rat in a Maze problem, we search for paths from the source cell to the destination cell while avoiding blocked or already visited cells. At each step, the rat chooses a valid move, explores deeper, and backtracks when stuck.

Rat in a Maze - Backtracking

public class RatInMaze {

    static int N;
    static int[][] maze;
    static int[][] solution;
    static int paths = 0;

    static int[] dr = {0, 1, 0, -1};
    static int[] dc = {1, 0, -1, 0};
    static String[] dir = {"R", "D", "L", "U"};

    static boolean isSafe(int r, int c) {
        return r >= 0 && r < N && c >= 0 && c < N
            && maze[r][c] == 1 && solution[r][c] == 0;
    }

    static void solve(int r, int c, String path) {
        if (r == N - 1 && c == N - 1) {
            paths++;
            System.out.println("Path " + paths + ": " + path);
            return;
        }

        solution[r][c] = 1;  // CHOOSE

        for (int d = 0; d < 4; d++) {
            int nr = r + dr[d];
            int nc = c + dc[d];
            if (isSafe(nr, nc)) {
                solve(nr, nc, path + dir[d]);  // EXPLORE
            }
        }

        solution[r][c] = 0;  // UNCHOOSE
    }

    public static void main(String[] args) {
        N = 4;
        maze = new int[][]{
            {1, 0, 0, 0},
            {1, 1, 0, 1},
            {0, 1, 0, 0},
            {0, 1, 1, 1}
        };
        solution = new int[N][N];

        System.out.println("All paths from (0,0) to (" + (N-1) + "," + (N-1) + "):");
        solve(0, 0, "");
        System.out.println("Total paths: " + paths);
    }
}

How Pruning Improves Backtracking

Pruning means rejecting a partial solution early. Good pruning can reduce the search space dramatically.

Problem	Pruning Rule
N-Queens	Reject positions that share a column or diagonal with an existing queen
Subset Sum	Stop if the current sum already exceeds the target for non-negative inputs
Rat in a Maze	Reject blocked cells or cells already in the current path
Sudoku	Reject digits that violate row, column, or subgrid constraints

Backtracking Complexity

Backtracking is usually exponential in the worst case because it may have to explore many branches. However, smart pruning often makes it much faster in practice.

Problem	Worst Case	Practical Notes
N-Queens	O(N!)	Pruning removes most invalid placements early
Subset Sum	O(2^n)	Pruning helps when the target can be exceeded quickly
Permutations	O(n!)	Must explore every arrangement if all outputs are required
Sudoku	Exponential	Constraint propagation reduces real search greatly
Graph Coloring	O(k^n)	Branching depends on number of colors and constraints

Common Backtracking Pattern in Words

Check whether the current state is already a complete solution.
Generate the next possible choices.
Skip any choice that immediately violates a rule.
Take one valid choice and recurse.
Undo that choice before trying the next one.

Backtracking Failure Cases

Forgetting to undo changes before returning from recursion.
Using unsafe pruning rules that remove valid solutions.
Not checking the base case correctly.
Mixing up backtracking with dynamic programming; backtracking explores possibilities, while DP stores repeated subproblem results.
Failing to mark and unmark visited states in path-search problems.

Backtracking vs Dynamic Programming

Aspect	Backtracking	Dynamic Programming
Main idea	Explore choices and undo bad ones	Reuse overlapping subproblem results
Typical goal	Search for valid solutions	Optimize value or count efficiently
Best for	Constraint satisfaction, enumeration, puzzles	Optimization with overlapping subproblems
Speed	Often exponential	Often polynomial or pseudo-polynomial after memoization/tabulation

Backtracking Rules

Backtracking is DFS over a decision tree with pruning.
The standard pattern is choose, explore, unchoose.
It is especially useful for constraint satisfaction and search problems.
Worst-case time is usually exponential, but pruning can make it practical.
Correct pruning and correct undo steps are the heart of a good backtracking solution.

Before you move on