N皇后问题如何写出简洁的最优解 - 回溯法及LeetCode应用详解

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

Note: A leaf is a node with no children.

Example:
Given the below binary tree and sum = 22,

      5/ \4   8/   / \11  13  4/  \      \
7    2      1

return true, as there exist a root-to-leaf path 5->4->11->2which sum is 22.

因为是树形结构，很容易联想到使用DFS递归来解：

// 112. Path Sum
/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/
public class PathSum {public boolean hasPathSum(TreeNode root, int sum) {if(root == null) return false;// Path value condition need that the last node must be a leaf nodeif((sum -= root.val) == 0 && root.left == null && root.right == null) {return true;}return hasPathSum(root.left, sum) || hasPathSum(root.right, sum);}
}

Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum.

Note: A leaf is a node with no children.

Example:
Given the below binary tree and sum = 22,

      5/ \4   8/   / \11  13  4/  \    / \
7    2  5   1

Return:

[[5,4,11,2],[5,8,4,5]
]

这道题是上面简单题的扩展版，从求有没有解到把所有的解都求出来，这个时候就需要回溯法了。因为DFS找到解之后就直接返回了，它无法穷举所有的情况。

// 113. Path Sum II/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/public class Solution {public List<List<Integer>> pathSum(TreeNode root, int sum) {List<List<Integer>> res = new ArrayList<>();dfs(root, sum, res, new ArrayList());return res;}public void dfs(TreeNode root, int sum, List<List<Integer>> res, List<Integer> list) {if(root == null) return; // 递归终止条件sum -= root.val;    // 需要回溯的操作1list.add(root.val); // 需要回溯的操作2if(root.left == null && root.right == null) {if(sum == 0) {res.add(new ArrayList(list));}list.remove(list.size()-1); // 回溯 取消操作2 把操作2加进去的元素删掉// sum += root.val;         // 回溯 取消操作1 不再向下递归 这一句做不做都一样return;}dfs(root.left, sum, res, list);dfs(root.right, sum, res, list);list.remove(list.size()-1);    // 回溯 取消操作2 把操作2加进去的元素删掉// sum += root.val;            // 回溯 取消操作1 因为不再向下递归 这一句做不做都一样}
}

回溯法比较难搞懂的是它的执行路径，因为它建立在递归之上，而且还有后悔操作。以这个例子为例，list.remove(list.size()-1)移除的到底是哪一个元素呢？没错，是本次递归所加进去的元素。递归调用会保存堆栈，两行dfs返回之后list的状态是没有执行两行dfs的状态，而不是执行了两行dfs之后的状态，这点是反直觉的。你可以把代码辅助到Idea中，打个断点，然后一步一步观察相关变量是如何变化的，以加深自己的理解。

下面我们在看看和的组合以及序列这两个LeetCode的回溯典型题：

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.

The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

It is guaranteed that the number of unique combinations that sum up to target is less than 150 combinations for the given input.

Example 1:
Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation:
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
7 is a candidate, and 7 = 7.
These are the only two combinations.

Example 2:
Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]

Example 3:
Input: candidates = [2], target = 1
Output: []

Example 4:
Input: candidates = [1], target = 1
Output: [[1]]

Example 5:
Input: candidates = [1], target = 2
Output: [[1,1]]

Constraints:
1 <= candidates.length <= 30
1 <= candidates[i] <= 200
All elements of candidates are distinct.
1 <= target <= 500

class Solution {public void backtrack(int[] candidates, int index, int target, List<Integer> list, List<List<Integer>> res) {if(target == 0) { // 递归终止条件res.add(new ArrayList(list));return;}for(int i=index; i<candidates.length; i++) { // 因为这道题 数组元素是可以重复利用的所以i从index开始 递归调用也会传入index 这点请注意if(target - candidates[i] < 0) {break;}target -= candidates[i]; // 需要回溯的操作1list.add(candidates[i]); // 需要回溯的操作2backtrack(candidates, i, target, list, res);target += candidates[i]; // 回溯操作1list.remove(list.size()-1); // 回溯操作2}}public List<List<Integer>> combinationSum(int[] candidates, int target) {List<List<Integer>> res = new ArrayList<>();Arrays.sort(candidates); // 需要对数组排序backtrack(candidates, 0, target, new ArrayList(), res);return res;}
}

这道题我们可以看出，解回溯题是，需要回溯的操作位于递归调用之前，递归调用之后应该立即取消这些操作。

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

Example 1:
Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Example 2:
Input: nums = [0,1]
Output: [[0,1],[1,0]]

Example 3:
Input: nums = [1]
Output: [[1]]

Constraints:

1 <= nums.length <= 6
-10 <= nums[i] <= 10
All the integers of nums are unique.

// 46. Permutations
// c++ offer next_permutation to generate next permutationclass Solution {List<Integer> temp;public List<List<Integer>> arr = new ArrayList();public List<List<Integer>> permute(int[] nums) {permute(nums, 0, nums.length-1);return arr;}private void permute(int nums[], int left, int right) {if(left == right) {temp = new ArrayList<Integer>();for(int k: nums) {temp.add(k);}arr.add(temp);} else {for(int i=left; i<=right; i++) {swap(nums, i, left); // 需要回溯的操作permute(nums, left+1, right);swap(nums, i, left);  // 回溯操作}}}private void swap(int[] nums, int i, int left) {int temp = nums[i];nums[i] = nums[left];nums[left] = temp;}

这道题体现了回溯法的穷举特性，以Example1为例，加到结果集arr顺序是[1,2,3] ->[1,3,2]->[2,1,3]->[2,3,1]->[3,2,1]->[3,1,2]。思考一下递归执行的整个过程是怎样的？

Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.

Example 1:
Input: nums = [1,1,2]
Output:
[[1,1,2], [1,2,1], [2,1,1]]

Example 2:
Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Constraints:
1 <= nums.length <= 8
-10 <= nums[i] <= 10

// 47. Permutations IIclass Solution {
public:vector<vector<int>> permuteUnique(vector<int>& nums) {sort(nums.begin(), nums.end());vector<vector<int>> res = {nums};// if(nums.size() == 0) return res;while(next_permutation(nums.begin(),nums.end())) {res.push_back(nums);}return res;}
};

开个玩笑！不过这道题我只写了Python版本的。使用Python内置的计数器对数组元素计数，然后用一个就减掉一个，减到0直接删除，计数器为空的时候即为所有的元素都使用完毕，加入到结果集中。Python的回溯法可以写一个内置函数，是一种闭包的形式，可以减少很多参数的传递，改变变量作用域是闭包的重要作用之一。

# 47. Permutations IIclass Solution:def permuteUnique(self, nums: List[int]) -> List[int]:counter = collections.Counter(nums)def dfs(cur):res = []if not counter: # 递归终止条件return [cur]for num in list(counter.keys()):counter[num] -= 1 # 需要回溯的操作if counter[num] == 0:del counter[num]res += dfs(cur + [num]) # 等价于 res.append(dfs(cur + [num]))counter[num] = counter.get(num, 0) + 1 # 回溯操作return resreturn dfs([])

最后，就是我们的主人公了，经典的N皇后问题。

The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens’ placement, where ‘Q’ and ‘.’ both indicate a queen and an empty space, respectively.

Example 1:

Input: n = 4
Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above
Example 2:

Input: n = 1
Output: [["Q"]]

Constraints:
1 <= n <= 9

如果你不太看得懂对角线规律是这么来的话，参见这里。

// 51. N-Queens// 回溯法模板题 + 找规律
// 回溯法适用于枚举问题，比如全排列、组合之类的
// 这些问题往往需要在枚举的所有情况中选择满足条件的情况生成解或者是求最优解 因此需要注意if判断条件删除一些不需要考虑的情况
// 回溯法和DFS、BFS的区别在于为了枚举 有回溯过程 即为了生成所有情况而还原某些操作 比如下面的操作1和操作2 都是需要回溯的操作
// 千万不能忘掉回溯 否则无法生成所有解 或者漏掉最优解的过程// i表示第i行 j表示第j列
// 规律 对角线坐标
// 斜对角线坐标 行列坐标差值永远相等 为了避免出现负值 使用i-j+n 为此 diag1的容量应为2n
// 反斜对角线左边 行列坐标的和永远相等 为了避免出现溢出 diag1的容量为2nclass Solution {public List<List<String>> res = new ArrayList<>();public List<List<String>> solveNQueens(int n) {char[][] board = new char[n][n];boolean[] col = new boolean[n];boolean[] diag1 = new boolean[n+n];boolean[] diag2 = new boolean[n+n];// 初始化棋盘for(int i=0; i<n; i++) {for(int j=0; j<n; j++) {board[i][j] = '.';}}solveNQueens(0, n, board, col, diag1, diag2);return res;}public void solveNQueens(int i, int n, char[][] board, boolean[] col, boolean[] diag1, boolean[] diag2) {if(i == n) { // 递归终止条件List<String> list = new ArrayList<>();for(int r=0; r<n; r++) {list.add(new String(board[r])); // 因为是传引用 所以要new出新的String加入list}res.add(list);return;}for(int j=0; j<n; j++) {if(!col[j] && !diag1[n-i+j] && !diag2[i+j]) {board[i][j] = 'Q'; // 需要回溯的操作1col[j] = diag1[n-i+j] = diag2[i+j] = true; // 需要回溯的操作2solveNQueens(i+1, n, board, col, diag1, diag2);col[j] = diag1[n-i+j] = diag2[i+j] = false; // 回溯操作2board[i][j] = '.'; // 回溯操作1}}}
}

The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.

Given an integer n, return the number of distinct solutions to the n-queens puzzle.

Example 1:

Input: n = 4
Output: 2
Explanation: There are two distinct solutions to the 4-queens puzzle as shown.

Example 2:
Input: n = 1
Output: 1

Constraints:

1 <= n <= 9

回溯解法一(非最优解)：

解法同51，只不过到达递归终止条件时，我们就计数。这不是最优解，仅仅求出解的数量可以通过取巧来节省穷举整个求解过程的某些计算过程，见下面的解法。

class Solution {public int res = 0;public void solveNQueens(int n) {char[][] board = new char[n][n];boolean[] col = new boolean[n];boolean[] diag1 = new boolean[n+n];boolean[] diag2 = new boolean[n+n];for(int i=0; i<n; i++) {for(int j=0; j<n; j++) {board[i][j] = '.';}}solveNQueens(0, n, board, col, diag1, diag2);}public void solveNQueens(int i, int n, char[][] board, boolean[] col, boolean[] diag1, boolean[] diag2) {if(i == n) {res++;}for(int j=0; j<n; j++) {if(!col[j] && !diag1[n-i+j] && !diag2[i+j]) {board[i][j] = 'Q';col[j] = diag1[n-i+j] = diag2[i+j] = true;solveNQueens(i+1, n, board, col, diag1, diag2);col[j] = diag1[n-i+j] = diag2[i+j] = false;board[i][j] = '.';}}}public int totalNQueens(int n) {solveNQueens(n);return res;}
}

回溯解法二(最优解)：

使用整型的二进制表示做标志位
用n个十进制数 即可表示棋盘 0表示可以放Q 1表示不能放Q一旦某一行被放置了Q 则该位置变为1 整行整列都不能放Q了 因而整行整列都变成1 对应for循环操作a
反对角线 不能放Q 对应循环操作b
对角线   不能放Q 对应循环操作c

// 使用整型的二进制表示做标志位
// 用n个十进制数 即可表示棋盘 0 表示可以放Q 1表示不能放Q// 一旦某一行被放置了Q 则该位置变为1 整行整列都不能放Q了 因而整行整列都变成1 对应for循环操作a
// 反对角线 不能放Q 对应循环操作b
// 对角线   不能放Q 对应循环操作c// 以n = 3为例
// 000b = 0
// 000b = 0
// 000b = 0// 我们在第一行第一列放置Q Q存的是1 我这里为了区别因为本列本行或者对角线放了Q而不能放的位置 写成了Q
// Q00b = 4
// 000  = 0
// 000  = 0// for循环a操作 使得
// Q11  = 7
// 100  = 4
// 100  = 4// for循环b操作 使得
// Q11  = 7
// 110  = 6
// 100  = 4// for循环c操作 使得
// Q11  = 7
// 110  = 6
// 101  = 5// 最终得到
// Q11  = 7
// 11Q  = 7
// 1Q1  = 7
// 只有这一种解class Solution {public int total = 0;public int totalNQueens(int[] queens, int len) {int total = 0;for(int i=0; i<queens.length; i++) {if((queens[len-1] & (1 << i)) == 0) {if(len == queens.length) {total += 1;} else {int[] rem = new int[queens.length-len];for(int j=len; j<queens.length; j++) {rem[j-len] = queens[j];            // 储存操作前状态 为了回溯queens[j] |= 1 << i;               // 操作aqueens[j] |= 1 << (i+j - len + 1); // 操作b 对角线规律 行列坐标和相等 -len+1 防止溢出nqueens[j] |= 1 << (i-j + len - 1); // 操作c 对角线规律 行列坐标差相等 +len-1 防止小于0}total += totalNQueens(queens, len+1);for(int j=len; j<queens.length; j++) {queens[j] = rem[j-len];            // 回溯操作 同时撤销了操作a、b、c}}}}return total;}public int totalNQueens(int n) {int[] queens = new int[n];return totalNQueens(queens, 1);}
}