- 回溯框架
- 22. 括号生成
- 46. 全排列
- 51. N 皇后
res= []
def backtrack(path, 选择列表):
if 满足结束条件:
res.add(path)
return
for 选择 in 选择列表:
做选择
backtrack(path, 选择列表)
撤销选择
22. 括号生成
括号的匹配规则：左右括号成对，所以符合要求的括号对为 2n。
接着嵌套回溯框架即可。
Java解法：
class Solution {
public List generateParenthesis(int n) {
List list = new ArrayList();
//回溯
backtrack(list, "", 0 ,0, n);
return list;
}
public void backtrack(List list, String str, int open, int close, int max){
//符合要求返回
if(str.length() == max * 2){
list.add(str);
return;
}
//先遍历左括号
if(open < max) backtrack(list, str + "(", open + 1, close, max);
//再遍历右括号
if(close < open) backtrack(list, str + ")", open, close + 1,max);
}
}
python 解法：
class Solution(object):
def generateParenthesis(self, n):
"""
:type n: int
:rtype: List[str]
"""
def generate(p, left, right, parens = []):
if left:
generate(p + '(', left - 1, right)
if right > left:
generate(p + ')', left, right - 1)
if not right:
parens += p,
return parens
return generate('', n, n)
46. 全排列
嵌套回溯框架，尝试枚举每一个排列组合。
Java 解法：
class Solution {
public List> permute(int[] nums) {
List> List = new ArrayList<>();
backtrack(List, new ArrayList<>(), nums);
return List;
}
public void backtrack(List> list, List tempList, int[] nums){
if(tempList.size() == nums.length){
list.add(new ArrayList<>(tempList));
}
for(int i = 0; i < nums.length; i++){
if(tempList.contains(nums[i])) continue;
tempList.add(nums[i]);
backtrack(list, tempList, nums);
tempList.remove(tempList.size() - 1);
}
}
}
python 解法：
class Solution:
def permute(self, nums):
def recursive(nums, perm=[], res=[]):
if not nums:
res.append(perm[::])
for i in range(len(nums)):
newNums = nums[:i] + nums[i+1:]
perm.append(nums[i])
recursive(newNums, perm, res)
perm.pop()
return res
return recursive(nums)
51. N 皇后
皇后的放置顺序：
- 皇后是一行一行从上往下放的，所以左下方，右下方和正下方不用检查（还没放皇后）
- 因为一行只会放一个皇后，所以每行不用检查，也就是最后只用检查上面，左上，右上三个方向。
接着嵌套回溯框架即可。
C++解法：
class Solution {
public:
vector> res;
vector> solveNQueens(int n) {
// '.' 表示空，'Q' 表示皇后，初始化空棋盘。
vector board(n, string(n, '.'));
backtrack(board, 0);
return res;
}
void backtrack(vector& board, int row){
if (row == board.size()){
res.push_back(board);
return;
}
int n = board[row].size();
for(int col= 0; col < n; col++){
if(!isValid(board, row, col)){
continue;
}
board[row][col] ='Q';
backtrack(board, row + 1);
board[row][col] ='.';
}
}
bool isValid(vector& board, int row, int col){
int n = board.size();
for(int i =0; i <= row; i++){
if (board[i][col] == 'Q')
return false;
}
// 检查左上方是否有皇后互相冲突
for (int i = row - 1, j = col - 1;
i >= 0 && j >= 0; i--, j--) {
if (board[i][j] == 'Q')
return false;
}
// 检查右上方是否有皇后互相冲突
for (int i = row - 1, j = col + 1;
i >= 0 && j < n; i--, j++) {
if (board[i][j] == 'Q')
return false;
}
return true;
}
};
Java 解法：
class Solution {
List> res = new ArrayList<>();
public List> solveNQueens(int n) {
// "." 表示空，"Q"表示皇后，初始化棋盘
char[][] board = new char[n][n];
for (char[] c : board) {
Arrays.fill(c, '.');
}
backtrack(board, 0);
return res;
}
public void backtrack(char[][] board, int row) {
// 每一行都成功放置了皇后，记录结果
if (row == board.length) {
res.add(charToList(board));
return;
}
int n = board[row].length;
// 在当前行的每一列都可能放置皇后
for (int col = 0; col < n; col++) {
// 排除可以相互攻击的格子
if (!isValid(board, row, col)) {
continue;
}
// 做选择
board[row][col] = 'Q';
// 进入下一行放皇后
backtrack(board, row + 1);
// 撤销选择
board[row][col] = '.';
}
}
public boolean isValid(char[][] board, int row, int col) {
int n = board.length;
// 检查列是否有皇后冲突
for (int i = 0; i < n; i++) {
if (board[i][col] == 'Q') {
return false;
}
}
// 检查右上方是否有皇后冲突
for (int i = row - 1, j = col + 1; i >=0 && j < n; i--, j++) {
if (board[i][j] == 'Q') {
return false;
}
}
// 检查左上方是否有皇后冲突
for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
if (board[i][j] == 'Q') {
return false;
}
}
return true;
}
public List charToList(char[][] board) {
List list = new ArrayList<>();
for (char[] c : board) {
list.add(String.copyValueOf(c));
}
return list;
}
}
