回溯

全排列、子集、组合

leetcode 46. 全排列

给定一个 没有重复 数字的序列，返回其所有可能的全排列。
示例:

输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

class Solution {
    List<List<Integer>> list = new ArrayList<>();
    public List<List<Integer>> permute(int[] nums) {
        // Arrays.sort(nums); // not necessary
        backtrack(new ArrayList<>(), nums,new boolean[nums.length]);
        return list;
    }

    private boolean backtrack(List<Integer> tempList, int[] nums,boolean[] visited) {
        if (tempList.size() == nums.length) {
            list.add(new ArrayList<>(tempList));
            return true;
        }
        for (int i = 0; i < nums.length; i++) {
            if (visited[i]) {
                continue; // element already exists, skip
            }
            visited[i] = true;
            tempList.add(nums[i]);
            if(backtrack(tempList, nums,visited)){
                return true;
            }
            visited[i] = false;
            tempList.remove(tempList.size() - 1);
        }
        return false;
    }
}

leetcode 78. 子集

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

示例:

输入: nums = [1,2,3]
输出:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();
        Arrays.sort(nums);
        backtrack(list, new ArrayList<>(), nums, 0);
        return list;
    }

    private void backtrack(List<List<Integer>> list , List<Integer> tempList, int [] nums, int start){
        list.add(new ArrayList<>(tempList));
        for(int i = start; i < nums.length; i++){
            tempList.add(nums[i]);
            backtrack(list, tempList, nums, i + 1);
            tempList.remove(tempList.size() - 1);
        }
    }
}

leetcode 77. 组合

给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。

示例:

输入: n = 4, k = 2
输出:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]

class Solution {
    public static List<List<Integer>> combine(int n, int k) {
		List<List<Integer>> combs = new ArrayList<List<Integer>>();
		combine(combs, new ArrayList<Integer>(), 1, n, k);
		return combs;
	}
	public static void combine(List<List<Integer>> combs, List<Integer> comb, int start, int n, int k) {
		if(k==comb.size()) {
			combs.add(new ArrayList<Integer>(comb));
			return;
		}
		for(int i=start;i<=n;i++) {
			comb.add(i);
			combine(combs, comb, i+1, n, k);
			comb.remove(comb.size()-1);
		}
	}
}

数独、N皇后

leetcode 37. 解数独

编写一个程序，通过已填充的空格来解决数独问题。

一个数独的解法需遵循如下规则：

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
空白格用 ‘.’ 表示。

class Solution {
    public void solveSudoku(char[][] board) {
        if (board == null || board.length == 0)
            return;
        backtrack(board,0,0);
    }

    boolean backtrack(char[][] board, int i, int j) {
        int m = 9, n = 9;
        if (j == n) {
            // 穷举到最后一列的话就换到下一行重新开始。
            return backtrack(board, i + 1, 0);
        }
        if (i == m) {
            // 找到一个可行解，触发 base case
            return true;
        }

        if (board[i][j] != '.') {
            // 如果有预设数字，不用我们穷举
            return backtrack(board, i, j + 1);
        } 

        for (char ch = '1'; ch <= '9'; ch++) {
            // 如果遇到不合法的数字，就跳过
            if (!isValid(board, i, j, ch))
                continue;

            board[i][j] = ch;
            // 如果找到一个可行解，立即结束
            if (backtrack(board, i, j + 1)) {
                return true;
            }
            board[i][j] = '.';
        }
        // 穷举完 1~9，依然没有找到可行解，此路不通
        return false;
    }


    private boolean isValid(char[][] board, int row, int col, char c) {
        for (int i = 0; i < 9; i++) {
            if (board[i][col] != '.' && board[i][col] == c) return false; //check row
            if (board[row][i] != '.' && board[row][i] == c) return false; //check column
            if (board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] != '.' &&
                    board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c) return false; //check 3*3 block
        }
        return true;
    }
}

leetcode 51. N皇后

class Solution {
  public List<List<String>> solveNQueens(int n) {
    char[][] chess = new char[n][n];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        chess[i][j] = '.';
      }
    }
    List<List<String>> res = new ArrayList<>();

    solve(res, chess, 0);
    return res;
  }

  private void solve(List<List<String>> res, char[][] chess, int row) {
    if (row == chess.length) {
      res.add(construct(chess));
      return;
    }
    for (int col = 0; col < chess.length; col++) {
      if (valid(chess, row, col)) {
        chess[row][col] = 'Q';
        solve(res, chess, row + 1);
        chess[row][col] = '.';
      }
    }
  }

  private boolean valid(char[][] chess, int row, int col) {
    // check all cols
    for (int i = 0; i < row; i++) {
      if (chess[i][col] == 'Q') {
        return false;
      }
    }
    //check 45 degree
    for (int i = row - 1, j = col + 1; i >= 0 && j < chess.length; i--, j++) {
      if (chess[i][j] == 'Q') {
        return false;
      }
    }
    //check 135
    for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
      if (chess[i][j] == 'Q') {
        return false;
      }
    }
    return true;
  }

  private List<String> construct(char[][] chess) {
    List<String> path = new ArrayList<>();
    for (int i = 0; i < chess.length; i++) {
      path.add(new String(chess[i]));
    }
    return path;
  }
}

括号

leetcode 22. 括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例：

输入：n = 3
输出：[
“((()))”,
“(()())”,
“(())()”,
“()(())”,
“()()()”
]

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<String>();
        backtrack(n,n,new StringBuilder(),res);
        return res;
    }

    public void backtrack(int left, int right, StringBuilder track,List<String> res){

        // 若左括号剩下的多，说明不合法
        if (right < left) return;
        // 数量小于 0 肯定是不合法的
        if (left < 0 || right < 0) return;
        // 当所有括号都恰好用完时，得到一个合法的括号组合
        if (left == 0 && right == 0) {
            res.add(track.toString());
            return;
        }
        
        // 尝试放一个左括号
        track.append('('); // 选择
        backtrack(left - 1, right, track, res);
        track.deleteCharAt(track.length() - 1); // 撤消选择

        // 尝试放一个右括号
        track.append(')'); // 选择
        backtrack(left, right - 1, track, res);
        track.deleteCharAt(track.length() - 1);// 撤消选择
    }

}