【LeetCode】回溯 N皇后
生活随笔
收集整理的這篇文章主要介紹了
【LeetCode】回溯 N皇后
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
總結
技巧：
-
子集和組合問題經常需要一個start來標記開始選擇的起始位置來達到去重的目的，排列問題不用 【46.全排列】
-
排列問題常需要一個used數組來標記已經選擇的元素（也可以同時用于去重）
C++ 總結了回溯問題類型 帶你搞懂回溯算法(大量例題)
- ①畫出遞歸樹，找到狀態變量(回溯函數的參數)，這一步非常重要※
- ②根據題意，確立結束條件
- ③找準選擇列表(與函數參數相關),與第一步緊密關聯※
- ④判斷是否需要剪枝
- ⑤作出選擇，遞歸調用，進入下一層
- ⑥撤銷選擇
【參考：回溯算法解題套路框架 :: labuladong的算法小抄】
46、51題
- 模版
- 切割問題類似于組合問題（131題、93題）
- 子集和組合問題一般for循環從start開始
- 排列問題一般for循環從0開始
- 比如{1,2}求排列:{1},{2},{1,2},{2,1}
- 去重先得對集合排序
C++ 總結了回溯問題類型 帶你搞懂回溯算法(排列篇)
- 【參考：回溯算法團滅排列/組合/子集問題_labuladong_微信公眾號】
【參考：回溯算法入門級詳解 + 練習（持續更新） - 全排列 - 力扣（LeetCode）】 巨詳細
去重——用set去重
【參考：代碼隨想錄# 回溯算法去重問題的另一種寫法】
中等
78.子集
【參考：78. 子集 - 力扣（LeetCode）】
class Solution {List<List<Integer>> res=new ArrayList<>();public List<List<Integer>> subsets(int[] nums) {List<Integer> track=new ArrayList<>(); //走過的路徑backtarck(nums,0,track);return res;}public void backtarck(int[] nums,int start,List<Integer> track){if (start > nums.length) {return;}res.add(new ArrayList<>(track));for(int i=start;i<nums.length;i++){// 做選擇（添加這個數）track.add(nums[i]);// 遞歸回溯（從i+1開始）backtarck(nums,i+1,track);// 撤銷選擇track.remove(track.size() - 1);}} }90. 子集 II
【參考：90. 子集 II - 力扣（LeetCode）】
需要去重
class Solution {List<List<Integer>> res=new ArrayList<>();public List<List<Integer>> subsetsWithDup(int[] nums) {List<Integer> track=new ArrayList<>();int[] used=new int[nums.length];Arrays.sort(nums);backtarck(nums,0,used,track);return res;}public void backtarck(int[] nums,int start,int[] used,List<Integer> track){if (start > nums.length) {return;}res.add(new ArrayList<>(track));for(int i=start;i<nums.length;i++){// 去重if(i>0 && nums[i]==nums[i-1] && used[i-1]==0){continue;}// 做選擇（添加這個數）track.add(nums[i]);used[i]=1;// 遞歸回溯（從i+1開始）backtarck(nums,i+1,used,track);// 撤銷選擇used[i]=0;track.remove(track.size() - 1);}} }77. 組合 ***
【參考：77. 組合 - 力扣（LeetCode）】
【參考：代碼隨想錄# 第77題. 組合】
【參考：回溯算法 + 剪枝（Java） - 組合 - 力扣（LeetCode）】 這個寫的巨詳細
class Solution {List<List<Integer>> res=new ArrayList<>();public List<List<Integer>> combine(int n, int k) {if(k<=0 || n<=0) return res;List<Integer> track=new ArrayList<>(); //走過的路徑backtarck(n,k,1,track);// start從1開始return res;}// 范圍 [1, n] 中所有可能的 k 個數的組合,start:從幾開始public void backtarck(int n,int k,int start,List<Integer> track){if(k==track.size()){res.add(new ArrayList<>(track));return;}for(int i=start;i<=n;i++){// 做選擇（添加這個數）track.add(i);System.out.println("遞歸之前 => " + track);// 遞歸回溯（從i+1開始）backtarck(n,k,i+1,track);// 撤銷選擇track.remove(track.size() - 1);System.out.println("遞歸之后 => " + track);}}public static void main(String[] args) {Solution solution = new Solution();int n = 5;int k = 3;List<List<Integer>> res = solution.combine(n, k);System.out.println(res);} }遞歸之前 => [1] 遞歸之前 => [1, 2] 遞歸之前 => [1, 2, 3] 遞歸之后 => [1, 2] 遞歸之前 => [1, 2, 4] 遞歸之后 => [1, 2] 遞歸之前 => [1, 2, 5] 遞歸之后 => [1, 2] 遞歸之后 => [1] 遞歸之前 => [1, 3] 遞歸之前 => [1, 3, 4] 遞歸之后 => [1, 3] 遞歸之前 => [1, 3, 5] 遞歸之后 => [1, 3] 遞歸之后 => [1] 遞歸之前 => [1, 4] 遞歸之前 => [1, 4, 5] 遞歸之后 => [1, 4] 遞歸之后 => [1] 遞歸之前 => [1, 5] 遞歸之后 => [1] 遞歸之后 => [] 遞歸之前 => [2] 遞歸之前 => [2, 3] 遞歸之前 => [2, 3, 4] 遞歸之后 => [2, 3] 遞歸之前 => [2, 3, 5] 遞歸之后 => [2, 3] 遞歸之后 => [2] 遞歸之前 => [2, 4] 遞歸之前 => [2, 4, 5] 遞歸之后 => [2, 4] 遞歸之后 => [2] 遞歸之前 => [2, 5] 遞歸之后 => [2] 遞歸之后 => [] 遞歸之前 => [3] 遞歸之前 => [3, 4] 遞歸之前 => [3, 4, 5] 遞歸之后 => [3, 4] 遞歸之后 => [3] 遞歸之前 => [3, 5] 遞歸之后 => [3] 遞歸之后 => [] 遞歸之前 => [4] 遞歸之前 => [4, 5] 遞歸之后 => [4] 遞歸之后 => [] 遞歸之前 => [5] 遞歸之后 => [] [[1, 2, 3], [1, 2, 4], [1, 2, 5], [1, 3, 4], [1, 3, 5], [1, 4, 5], [2, 3, 4], [2, 3, 5], [2, 4, 5], [3, 4, 5]]作者：liweiwei1419 鏈接：https://leetcode-cn.com/problems/combinations/solution/hui-su-suan-fa-jian-zhi-python-dai-ma-java-dai-ma-/剪枝優化
【參考：代碼隨想錄# 第77題. 組合-剪枝優化】
- 已經選擇的元素個數：path.size();
- 還需要的元素個數為: k - path.size();
- 在集合n中起始位置i最大為 : n - (k - path.size()) + 1
為什么有個+1呢，因為包括起始位置，我們要是一個左閉的集合。
舉個例子，n = 4，k = 2， 目前已經選取的元素為0（path.size為0），n - (k - 0) + 1 即 4 - ( 2 - 0) + 1 = 3。i最大從3開始搜索 （組合[3, 4]）。也就是說 i∈[1,3]i\in[1,3]i∈[1,3]
這里大家想不懂的話，建議也舉一個例子，就知道是不是要+1了。
for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) // i為本次搜索的起始位置216. 組合總和 III
【參考：216. 組合總和 III - 力扣（LeetCode）】
class Solution {List<List<Integer>> res=new ArrayList<>();public List<List<Integer>> combinationSum3(int k, int n) {List<Integer> track=new ArrayList<>(); //走過的路徑backtarck(k,n,1,0,track);return res;}// sum 為已經收集的元素之和public void backtarck(int k, int n,int start,int sum,List<Integer> track){if(sum==n&&track.size()==k){res.add(new ArrayList<>(track));return;} for(int i=start;i<10;i++){// 做選擇（添加這個數）track.add(i);sum += i;// 遞歸回溯backtarck(k,n,i+1,sum,track); // 注意下一步start=i+1// 撤銷選擇sum -= i;track.remove(track.size() - 1);}} }39. 組合總和
【參考：39. 組合總和 - 力扣（LeetCode）】
class Solution {List<List<Integer>> res=new ArrayList<>();public List<List<Integer>> combinationSum(int[] candidates, int target) {List<Integer> track=new ArrayList<>(); //走過的路徑backtarck(candidates,target,0,0,track);return res;}public void backtarck(int[] candidates,int target,int sum,int start,List<Integer> track){if (sum > target) {return;}if(sum==target){res.add(new ArrayList<>(track));return;}for(int i=start;i<candidates.length;i++){// 做選擇track.add(candidates[i]);sum+=candidates[i];// 注意可以重復讀取當前的數，所以下一次start=ibacktarck(candidates,target,sum,i,track);// 遞歸回溯// 撤銷選擇sum-=candidates[i];track.remove(track.size() - 1);}} }- 剪枝
40.組合總和 II ***
【參考：40. 組合總和 II - 力扣（LeetCode）】
使用used[]去重（具有普適性）
【參考：代碼隨想錄# 40.組合總和II】
我在圖中將used的變化用橘黃色標注上，可以看出在candidates[i] == candidates[i - 1]相同的情況下：
- used[i - 1] == 1，說明同一樹枝candidates[i - 1]使用過
- used[i - 1] == 0，說明同一樹層candidates[i - 1]使用過（前一個樹枝使用過）
前提：為了將重復的數字都放到一起，要先進行排序
boolean[] used = new boolean[n];// 默認為false
class Solution {List<List<Integer>> res=new ArrayList<>();List<Integer> track=new ArrayList<>(); //走過的路徑public List<List<Integer>> combinationSum2(int[] candidates, int target) {Arrays.sort(candidates);// 先排序//加標志數組，用來輔助判斷同層節點是否已經遍歷int[] used = new int[candidates.length];// 默認為0backtarck(candidates,target,0,0,used);return res;}public void backtarck(int[] candidates,int target,int sum,int start,int[] used){if (sum > target) {return;}if(sum==target){res.add(new ArrayList<>(track));return;}for(int i=start;i<candidates.length;i++){if (i > 0 && candidates[i] == candidates[i - 1] && used[i-1] == 0) {continue;}// 做選擇track.add(candidates[i]);sum+=candidates[i];used[i]=1;// 遞歸回溯backtarck(candidates,target,sum,i+1,used);// 下一次start=i+1// 撤銷選擇used[i]=0; sum-=candidates[i];track.remove(track.size() - 1);}} }直接使用start去重
【參考：回溯算法 + 剪枝（Java、Python） - 組合總和 II - 力扣（LeetCode）】
解釋語句: if cur > begin and candidates[cur-1] == candidates[cur] 是如何避免重復的。
【參考：回溯算法 + 剪枝（Java、Python） - 組合總和 II 高贊評論 - 力扣（LeetCode）】
17. 電話號碼的字母組合
【參考：17. 電話號碼的字母組合 - 力扣（LeetCode）】
class Solution {//初始對應所有的數字，為了直接對應2-9，新增了兩個無效的字符串""String letterMap[] = {" ", //0"", //1"abc", //2"def", //3"ghi", //4"jkl", //5"mno", //6"pqrs", //7"tuv", //8"wxyz" //9};List<String> reslut=new ArrayList<>();StringBuilder sb=new StringBuilder();public List<String> letterCombinations(String digits) {if(digits.length()==0){return reslut;}backTracking(digits,0);return reslut;}// 下標index表示digits中第index+1個字符public void backTracking(String digits,int index){if(index==digits.length()){reslut.add(sb.toString());// 添加return;}int num=digits.charAt(index)- '0';// 比如 '2'-'0'= 2String letter=letterMap[num];// 數字對于的字符串for(char c: letter.toCharArray()){sb.append(c);backTracking(digits,index+1);// 遞歸sb.deleteCharAt(sb.length()-1);// 回溯}} }131. 分割回文串
【參考：131. 分割回文串 - 力扣（LeetCode）】
【參考：代碼隨想錄# 131.分割回文串】
class Solution {List<List<String>> result = new ArrayList<>();List<String> path = new ArrayList<>(); public List<List<String>> partition(String s) {backtarck(s, 0);return result;}public void backtarck(String s, int start) {if (start > s.length()) {return;}if (start == s.length()) {result.add(new ArrayList<>(path));return;}for (int i = start; i < s.length(); i++) {// 不是回文則跳過if (!isPalindrome(s, start, i)) {continue;}// 做選擇path.add(s.substring(start, i + 1));// +1 是因為substring函數是[)// 遞歸回溯backtarck(s, i + 1);// 撤銷選擇path.remove(path.size() - 1);}}public boolean isPalindrome(String s, int left, int right) {while (left < right) {if (s.charAt(left) != s.charAt(right)) {return false;}left++;right--;}return true;} }93. 復原 IP 地址（難）
【參考：93. 復原 IP 地址 - 力扣（LeetCode）】
【參考：代碼隨想錄# 93.復原IP地址】
class Solution {List<String> result = new ArrayList<>();List<String> path = new ArrayList<>(); //走過的路徑public List<String> restoreIpAddresses(String s) {// 如果長度不符合int len = s.length();if (len < 4 || len > 12) {return result;}backtarck(s, 0, 0);return result;}public void backtarck(String s, int start, int pointNum) {if (pointNum == 3) {// 逗點數量為3時，分隔結束// 判斷第四段?字符串是否合法，如果合法就放進result中if (isValid(s, start, s.length() - 1)) {result.add(s);}return;}for (int i = start; i < s.length(); i++) {if (!isValid(s, start, i)) {break;} else {// substring:1.[beginIndex, endIndex) 2.beginIndex至末尾s = s.substring(0, i + 1) + "." + s.substring(i + 1); //在str的后?插??個逗點pointNum++;// 點的數量加一backtarck(s, i + 2, pointNum);// 插?點之后下?個?串的起始位置為i+2pointNum--;// 回溯s = s.substring(0, i + 1) + s.substring(i + 2);// 回溯刪掉點}}}// 判斷字符串s在左閉?閉區間[start, end]所組成的數字是否合法private Boolean isValid(String s, int start, int end) {if (start > end) {return false;}if (s.charAt(start) == '0' && start != end) { // 0開頭的數字不合法return false;}int num = 0;for (int i = start; i <= end; i++) {if (s.charAt(i) > '9' || s.charAt(i) < '0') { // 遇到?數字字符不合法return false;}num = num * 10 + (s.charAt(i) - '0');if (num > 255) { // 如果?于255了不合法return false;}}return true;} }491. 遞增子序列（難）
【參考：491. 遞增子序列 - 力扣（LeetCode）】
【參考：代碼隨想錄# 491.遞增子序列】
需要去重，但不能重新排序
set去重那塊不太好理解，待回顧
【參考：代碼隨想錄# 回溯算法去重問題的另一種寫法】
46. 全排列 ***
【參考：46. 全排列 - 力扣（LeetCode）】
【參考：回溯算法解題套路框架 :: labuladong的算法小抄】
// labuladong List<List<Integer>> res = new LinkedList<>();/* 主函數，輸入一組不重復的數字，返回它們的全排列 */ List<List<Integer>> permute(int[] nums) {// 記錄「路徑」LinkedList<Integer> track = new LinkedList<>();backtrack(nums, track);return res; }// 路徑：記錄在 track 中 // 選擇列表：nums 中不存在于 track 的那些元素 // 結束條件：nums 中的元素全都在 track 中出現 void backtrack(int[] nums, LinkedList<Integer> track) {// 觸發結束條件if (track.size() == nums.length) {res.add(new LinkedList(track));return;}for (int i = 0; i < nums.length; i++) {// 排除不合法的選擇if (track.contains(nums[i])) {continue;}// 做選擇track.add(nums[i]);// 進入下一層決策樹backtrack(nums, track);// 取消選擇track.removeLast();} }【參考：代碼隨想錄# 46.全排列】
class Solution {List<List<Integer>> result=new ArrayList<>();List<Integer> path=new ArrayList<>(); public List<List<Integer>> permute(int[] nums) {//加標志數組，用來輔助判斷int[] used = new int[nums.length];// 默認為0backtarck(nums,used);return result;}public void backtarck(int[] nums,int[] used){if(path.size()==nums.length){result.add(new ArrayList<>(path));return;}for(int i=0;i<nums.length;i++){if (used[i] == 1) {// path中已經收錄的元素，直接跳過continue;}// 做選擇path.add(nums[i]);used[i]=1;backtarck(nums,used);// 遞歸回溯// 撤銷選擇used[i]=0; path.remove(path.size() - 1);}} }47. 全排列 II
【參考：47. 全排列 II - 力扣（LeetCode）】
需要去重
class Solution {List<List<Integer>> result=new ArrayList<>();List<Integer> path=new ArrayList<>(); public List<List<Integer>> permuteUnique(int[] nums) {Arrays.sort(nums);// 先排序//加標志數組，用來輔助判斷int[] used = new int[nums.length];// 默認為0backtarck(nums,used);return result;}public void backtarck(int[] nums,int[] used){if(path.size()==nums.length){result.add(new ArrayList<>(path));return;}for(int i=0;i<nums.length;i++){// 去重if (i > 0 && nums[i] == nums[i - 1] && used[i-1] == 0) {continue;}if (used[i] == 1) {// path中已經收錄的元素，直接跳過continue;}// 做選擇path.add(nums[i]);used[i]=1;backtarck(nums,used);// 遞歸回溯// 撤銷選擇used[i]=0; path.remove(path.size() - 1);}} }困難
51. N 皇后 ***
【參考：51. N 皇后 - 力扣（LeetCode）】
【參考：回溯算法解題套路框架 :: labuladong的算法小抄】
這個問題本質上跟全排列問題差不多，決策樹的每一層表示棋盤上的每一行；每個節點可以做出的選擇是，在該行的任意一列放置一個皇后。
因為 C++ 代碼對字符串的操作方便一些，所以這道題我用 C++ 來寫解法，直接套用回溯算法框架:
vector<vector<string>> res;/* 輸入棋盤邊長 n，返回所有合法的放置 */ vector<vector<string>> solveNQueens(int n) {// '.' 表示空，'Q' 表示皇后，初始化空棋盤。vector<string> board(n, string(n, '.'));backtrack(board, 0);return res; }// 路徑：board 中小于 row 的那些行都已經成功放置了皇后 // 選擇列表：第 row 行的所有列都是放置皇后的選擇 // 結束條件：row 超過 board 的最后一行 void backtrack(vector<string>& 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] = '.';} }/* 是否可以在 board[row][col] 放置皇后？ */ bool isValid(vector<string>& board, int row, int col) {int n = board.size();// 檢查列是否有皇后互相沖突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; }只想要一個答案，怎么辦呢？
只要找到一個答案，for 循環的后續遞歸窮舉都會被阻斷。
【參考：代碼隨想錄# 第51題. N皇后】
class Solution {List<List<String>> result = new ArrayList<>();List<String> chessboard = new ArrayList<>();public List<List<String>> solveNQueens(int n) {// "." 表示空，"Q"表示皇后，初始化棋盤char[][] board = new char[n][n];for (char[] c : board) {Arrays.fill(c, '.');}backtrack(n, 0, board);return result;}// row 記錄當前遍歷到棋盤的第row+1層public void backtrack(int n, int row, char[][] board) {// 準備開始遍歷到n+1行時，表明此時棋盤已鋪滿（row從0開始）if (row == n) {result.add(charToList(board));}// 按行遍歷for (int col = 0; col < n; col++) {if (isVaild(row, col, n, board)) {board[row][col] = 'Q'; // 放置皇后backtrack(n, row + 1, board);// 遞歸下一行board[row][col] = '.'; // 回溯 撤銷皇后}}}public boolean isVaild(int row, int col, int n, char[][] board) {// 檢查列(正上方)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;}public List<String> charToList(char[][] board) {List<String> list = new ArrayList<>();for (char[] c : board) {// System.out.println(String.valueOf(c));list.add(String.valueOf(c));}// System.out.println();return list;} } .Q.. ...Q Q... ..Q...Q. Q... ...Q .Q..37. 解數獨
【參考：37. 解數獨 - 力扣（LeetCode）】
【參考：回溯算法最佳實踐：解數獨 :: labuladong的算法小抄】
【參考：代碼隨想錄# 37. 解數獨】
有點沒看懂 待回顧
class Solution {public void solveSudoku(char[][] board) {solveSudokuHelper(board);}private boolean solveSudokuHelper(char[][] board){//「一個for循環遍歷棋盤的行，一個for循環遍歷棋盤的列，// 一行一列確定下來之后，遞歸遍歷這個位置放9個數字的可能性！」for (int i = 0; i < 9; i++){ // 遍歷行for (int j = 0; j < 9; j++){ // 遍歷列if (board[i][j] != '.'){ // 跳過原始數字continue;}for (char k = '1'; k <= '9'; k++){ // (i, j) 這個位置放k是否合適if (isValidSudoku(i, j, k, board)){board[i][j] = k;if (solveSudokuHelper(board)){ // 如果找到合適一組立刻返回return true;}board[i][j] = '.';}}// 9個數都試完了，都不行，那么就返回falsereturn false;// 因為如果一行一列確定下來了，這里嘗試了9個數都不行，說明這個棋盤找不到解決數獨問題的解！// 那么會直接返回， 「這也就是為什么沒有終止條件也不會永遠填不滿棋盤而無限遞歸下去！」}}// 遍歷完沒有返回false，說明找到了合適棋盤位置了return true;}/*** 判斷棋盤是否合法有如下三個維度:* 同行是否重復* 同列是否重復* 9宮格里是否重復*/private boolean isValidSudoku(int row, int col, char val, char[][] board){// 同行是否重復for (int i = 0; i < 9; i++){if (board[row][i] == val){return false;}}// 同列是否重復for (int j = 0; j < 9; j++){if (board[j][col] == val){return false;}}// 9宮格里是否重復int startRow = (row / 3) * 3;int startCol = (col / 3) * 3;for (int i = startRow; i < startRow + 3; i++){for (int j = startCol; j < startCol + 3; j++){if (board[i][j] == val){return false;}}}return true;} }總結
以上是生活随笔為你收集整理的【LeetCode】回溯 N皇后的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 番茄工作法总结-第三章:方法
- 下一篇： 开发人员学习文档下载地址