Backtracking

According to wikipedia,

Backtracking is general algorithm for finding all (or some) solutions to some computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons a candidate (backtracks) as soon as it determines that the candidate cannot possibly be completed to a valid solution.

I have compared backtracking to DFS in a previous post, so here I’ll just focus on the classic problems solved by backtracking.

I. Permutation

46. Permutations: return all possible permutations given a list of distinct numbers.

This is a simple but classic problem. It has many different solutions, not limited to the ones I provide below. And the ideas of the solutions can be applied to many other problems.

Solution 1: simulate the way that we create permutations.
Suppose there are {1, 2, 3}, we can use all these numbers for Position 0; if we pick 1, then Poisition 1 is left with {2, 3}; if we pick 3 for Position 1, then we leave Position 2 with 2; so we have one permutation {1, 3, 2}. And then we backtrack, repeat the above process with different selections, and we’ll get another permutation.

void dfs(int i, int[] permutation, int[] numbers, int[] mark) {
    if (i == numbers.length) {
        // print permutation as one possible permutation
        return;
    }
    for (int j = 0; j < numbers.length; j++) {
        if (mark[j] == 0) {
            mark[j] = 1; // mark if this number has been used or not
            permutation[i] = numbers[j];
            dfs(i + 1, permutation, numbers, mark);
            mark[j] = 0;
        }
    }
}

Solution 2: in-place swap.

void dfs(int i, int[] numbers) {
    if (i == numbers.length - 1) {
        // print numbers as one possible permutation
        return;
    }
    dfs(i + 1, numbers);
    for (int j = i + 1; j < numbers.length; j++) {
        swap(i, j, numbers);
        dfs(i + 1, numbers);
        swap(i, j, numbers);
    }
}

Solution 3: another implementation of in-place swap.

void dfs(int i, int[] numbers) {
    if (i == numbers.length - 1) {
        // print numbers as one possible permutation
        return;
    }
    for (int j = i; j < numbers.length; j++) {
        swap(i, j, numbers);
        dfs(i + 1, Arrays.copyOf(numbers, numbers.length));
    }
}

Solutioin 2 vs. Solution 3:

• The permutations generated by Solution 2 are not in lexicographical order; but the ones generated by Solution 3 are in lexicogrphical order
• For Solution 3, the numbers being swapped are adjacent in the original array

What causes the differences is that Solution 3 does not recover the order of numbers[i] and numbers[j] by using swap again and it makes a copy of the array so that the changes do not affect the array at the upper level.

Here is the process of applying Solution 2:

i	j	numbers	output
0	0	1, 2, 3
1	1	1, 2, 3	x
1	2	1, 3, 2	x
0	1	2, 1, 3
1	1	2, 1, 3	x
1	2	2, 3, 1	x
0	2	3, 2, 1
1	1	3, 2, 1	x
1	2	3, 1, 2	x

Here is the process of applying Solution 3:

i	j	numbers	output
0	0	1, 2, 3
1	1	1, 2, 3	x
1	2	1, 3, 2	x
0	1	2, 1, 3
1	1	2, 1, 3	x
1	2	2, 3, 1	x
0	2	3, 1, 2
1	1	3, 1, 2	x
1	2	3, 2, 1	x

When i = 0 and j = 2, Solution 2 does the swap based on {1, 2, 3}, but Solution 3 is based on the result of swapping numbers[0] and numbers[1], that is, {2, 1, 3}, and that makes all the differences.

Note that the time complexity for the solutions above is O(n!).

Follow-up: 47. Permutations II, the list of numbers might contain duplicates, but the permutations are required to be unique.

It is natural to figure out a solution to make use of Solution 3 that we can compare the two numbers before swap them, if they are equal, we will just skip the swap and move the the next number, so what we need to do is to sort the array to make sure that the duplicates are adjacent.

II. N-Queen

51. N-Queens: place n queens on an *nxn chessboard such that no two queens attack each other.

The idea is quite straightforward: place a queen on each row and try one row after another, if it does not work, backtrack to the last row and try another column. The key is to mark down which cells cannot be used when a queen is placed on the chessboard and unmark them when it is removed from the chessboard, as shown in the figure below.

void queen(int row, int n, int[][] marks) {
    if (row == n) {
        // this is a solution of N-Queen
        return;
    }
    for (int col = 0; col < n; col++) {
        if (marks[row][col] == 0) {
            mark(row, col, n, marks);
            queen(row + 1, n, marks);
            unmark(row, col, n, marks);
        }
    }
}

void mark(int row, int col, int n, int[][] marks) {
    for (int i = 0; i < n; i++) marks[row][i]--;
    for (int i = 0; i < n; i++) marks[row][i]--;
    // for simplification, there is no need to mark the cells in the upper rows
    int i = row + 1, j = col - 1;
    while (i < n && j >= 0) marks[i++][j--]--;
    i = row + 1, j = col + 1;
    while (i < n && j < n) marks[i++][j++]--;
}

void unmark(int row, int col, int n, int[][] marks) {
    for (int i = 0; i < n; i++) marks[row][i]++;
    for (int i = 0; i < n; i++) marks[row][i]++;
    int i = row + 1, j = col - 1;
    while (i < n && j >= 0) marks[i++][j--]++;
    i = row + 1, j = col + 1;
    while (i < n && j < n) marks[i++][j++]++;
}

The time complexity is O(n!).

III. Sudoku

37. Sudoku Solver: solve a Suduku puzzle.

The solution of sudoku is similar to the one of the N-queen problem, but a bit complicated. There are only two possibilites for each cell in the N-queen problem: a queen is placed in it or not; but for Sudoku, there are 9 possibilities, so we need to maintain the state of these 9 possibilities for each cell. When a number is filled in an empty cell, we need to update state for cells on the same row or on the same column or in the same block.
The time complexity is O(9^n).

public void solveSudoku(char[][] board) {
    int row = board.length;
    int col = board[0].length;
    int[][] marks = new int[row * col][9];
    init(marks, board);

    dfs(0, 0, row, col board, marks);
}

private boolean dfs(int i, int j, int row, int col, char[][] board, int[][] marks) {
    if (i == row) return true;

    int nI = (i + 1) % row;
    int nJ = nI == 0 ? j + 1 : j;
    if (board[i][j] == '.') {
        int k = i * col + j;
        for (int t = 0; t < 9; t++) {
            if (marks[k][t] == 0) {
                mark(i, j, t + 1, row, col, marks);
                board[i][j] = (char)(t + '1');
                if (dfs(nI, nJ, row, col, board, marks)) return true;
                unmark(i, j, t + 1, row, col, marks);
                board[i][j] = '.';
            }
        }
    } else {
        return dfs(nI, nJ, row, col, board, marks);
    }

    return false;
}

IV. More

17. Letter Combinations of a Phone Number: the Solution 1 of permutation can be directly applied to the problem.

22. Generate Parentheses: given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

// make sure that each combination starts with '('
dfs(1, 1, n, new StringBuilder('(')));

private void dfs(int totalLeft, int currentLeft, int n, StringBuilder parentheses) {
    if (totalLeft == n) {
        String result = addRightParenthesis(parentheses, n - currentLeft);
        return;
    }

    dfs(totalLeft + 1, currentLeft + 1, n, parentheses.append('(')));
    parentheses.deleteCharAt(parentheses.length() - 1);

    if (currentLeft > 0) {
        dfs(totalLeft, currentLeft - 1, n, parentheses.append(')')));
        parentheses.deleteCharAt(parentheses.length() - 1);
    }
}

The time complexity is O(2^2n).