當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

回溯（backtrack）

發布時間：2023/12/10 编程问答 30 豆豆

生活随笔收集整理的這篇文章主要介紹了回溯（backtrack）小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

回溯（backtrack）

- 1 回溯法思路
- 2 常見題目
- - 2.1 (lee-78) 子集
  - 2.2 (lee-90) 子集2
  - 2.3 (lee-46) 全排列
  - 2.4 (lee-47) 全排列2
  - 2.5 (lee-39) 組合總和
  - 2.6 (lee-40) 組合總和2
  - 2.7 (lee-93) 復原IP地址
  - 2.8 (lee-17) 電話號碼的字母組合
  - 2.9 (lee-131) 分割回文串
  - 2.10 (lee-79) 單詞搜索
  - 2.11 (lee-200) 島嶼數量
  - 2.12 (lee-JZ13)機器人的運動范圍
  - 2.13 (lee-JZ38) 字符串的排列
- 3 練習鏈接

（JAVA版本）

1 回溯法思路

常用于遍歷列表所有子集，是 DFS 深度搜索一種，一般用于全排列，窮盡所有可能，遍歷的過程實際上是一個決策樹的遍歷過程。時間復雜度一般 O(N!)，它不像動態規劃存在重疊子問題可以優化，回溯算法就是純暴力窮舉，復雜度一般都很高。
思路：核心就是從選擇列表里做一個選擇，然后一直遞歸往下搜索答案，如果遇到路徑不通，就返回來撤銷這次選擇。

偽代碼結構：

int[] result = new int[size];void backtrack(選擇列表,路徑): {if 滿足結束條件: {result.add(路徑)return}for (選擇 : 選擇列表): {做選擇backtrack(選擇列表,路徑)撤銷選擇}}

說明：
在后面的題目中，我們會頻繁的看到visited[]以及start變量，有些朋友可能會疑惑什么時候使用 visited 數組，什么時候使用 start 變量？總結如下：

排列問題，講究順序（即 [2, 2, 3] 與 [2, 3, 2] 視為不同列表時），需要記錄哪些數字已經使用過，此時用visited 數組；
組合問題，不講究順序（即 [2, 2, 3] 與 [2, 3, 2] 視為相同列表時），需要按照某種順序搜索，此時使用start 變量。

2 常見題目

2.1 (lee-78) 子集

給定一組不含重復元素的整數數組 nums，返回該數組所有可能的子集（冪集）。可以按任意順序返回解集。
思路：回溯法

輸入：nums = [1,2,3]
輸出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

（1）按任意順序返回

/*** 1.按任意順序返回*/public ArrayList<ArrayList<Integer>> subsets1(int[] S) { ArrayList<ArrayList<Integer>> res = new ArrayList<>();LinkedList<Integer> track = new LinkedList<>();back(res,S,0,track);return res; } private void back(ArrayList<ArrayList<Integer>> res,int[] S, int start, LinkedList<Integer> track) {res.add(new ArrayList<>(track));for(int i = start;i < S.length;i++) {track.add(S[i]); //更新狀態back(res,S,i+1,track); //回溯track.removeLast(); //回退狀態} }

（2）按一定順序返回

/*** 2.按一定順序返回*/public List<List<Integer>> subsets(int[] nums) {List<List<Integer>> res = new ArrayList<>();for(int i = 0;i <= nums.length ;i++) { //i是某個子集內的元素個數backtrack(res,0,new ArrayList<Integer>(),nums,i); }return res; }private void backtrack(List<List<Integer>> res, int first, ArrayList<Integer> cur, int[] nums,int k) {if(cur.size()== k) {res.add(new ArrayList<>(cur));return ;}for(int i = first;i < nums.length;i++) {cur.add(nums[i]);backtrack(res,i+1, cur, nums,k);cur.remove(cur.size()-1); // 刪除最后添加的一個數}}public static void main(String[] args) {Subsets s = new Subsets();Scanner in = new Scanner(System.in);String[] str = in.nextLine().split(" ");int[] nums = new int[str.length];for(int i = 0;i <nums.length;i++) {nums[i] = Integer.parseInt(str[i]);}List<List<Integer>> res = s.subsets(nums);System.out.println(res);}

2.2 (lee-90) 子集2

給你一個整數數組 nums ，其中可能包含重復元素，請你返回該數組所有可能的子集（冪集）。解集不能包含重復的子集。返回的解集中，子集可以按任意順序排列。

輸入：nums = [1,2,2]
輸出：[[],[1],[1,2],[1,2,2],[2],[2,2]]

import java.util.ArrayList; import java.util.Arrays; import java.util.List; import java.util.Scanner;public class Subsets2 {/*** 思路：重復的解不添加進去，并用一個數組visited標記某個元素是否被訪問過*/public List<List<Integer>> subsetsWithDup(int[] nums) {List<List<Integer>> res = new ArrayList<>();Arrays.sort(nums); //先將數組排序List<Integer> temp = new ArrayList<>();for(int i= 0;i <= nums.length;i++) {backtrack(res,temp,new boolean[nums.length],nums,0,i);}return res;}/** * @param res 所有子集* @param temp * @param visited 標記元素* @param nums * @param start* @param size*/private void backtrack(List<List<Integer>> res, List<Integer> temp, boolean[] visited, int[] nums, int start, int size) {if(temp.size() == size) {res.add(new ArrayList<>(temp));return;}for(int i = start; i <nums.length;i++) {if(i != 0 && nums[i] == nums[i-1] && !visited[i-1]) { //若發現沒有選擇上一個數，且當前數字與上一個數相同且前一個數沒有被標記過，則可以跳過當前生成的子集。。continue;}temp.add(nums[i]);visited[i] = true;backtrack(res, temp, visited, nums, i+1, size); //根據與前面元素是否重復，來決定start的取值，也就是開始遍歷的位置visited[i] = false;temp.remove(temp.size()-1);} }public static void main(String[] args) {Subsets2 s = new Subsets2();Scanner in = new Scanner(System.in);String[] str = in.nextLine().split(" ");int[] nums = new int[str.length];for(int i = 0;i <nums.length;i++) {nums[i] = Integer.parseInt(str[i]);}List<List<Integer>> res = s.subsetsWithDup(nums);System.out.println(res);} }

2.3 (lee-46) 全排列

給定一個沒有重復數字的序列，返回其所有可能的全排列。可以按任意順序返回答案。

輸入：nums = [1,2,3]
輸出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

/*** 思路：需要用一個visited數組記錄已經選擇過的元素，滿足條件的結果才進行返回* @param nums* @return*/public List<List<Integer>> permute(int[] nums) {List<List<Integer>> res = new ArrayList<>();List<Integer> permute = new ArrayList<>();boolean[] visited = new boolean[nums.length];backtrack(res,permute,visited,nums);return res;}/*** @param res 返回結果* @param permute * @param visited 記錄以及選擇過的元素* @param nums 數組*/private void backtrack(List<List<Integer>> res, List<Integer> permute, boolean[] visited, int[] nums) {if(permute.size() == nums.length) { //滿足結束條件res.add(new ArrayList<>(permute));return ;}for(int i = 0;i < visited.length;i++) {if(visited[i]) {continue;}visited[i] = true; //做選擇permute.add(nums[i]); backtrack(res, permute, visited, nums);visited[i] = false;//撤銷選擇 permute.remove(permute.size() - 1); }}

2.4 (lee-47) 全排列2

給定一個可包含重復數字的序列，返回所有不重復的全排列。
時間復雜度為 O(n×n!)
空間復雜度 O(n)

輸入：nums = [1,1,2]
輸出：[[1,1,2], [1,2,1], [2,1,1]]

public List<List<Integer>> permuteUnique(int[] nums) {List<List<Integer>> res = new ArrayList<>();List<Integer> permute = new ArrayList<>();Arrays.sort(nums);boolean[] visited = new boolean[nums.length];backtrack(res,permute,visited,nums);return res;}private void backtrack(List<List<Integer>> res, List<Integer> permute, boolean[] visited, int[] nums) {if(permute.size() == nums.length) {res.add(new ArrayList<>(permute));return;}for(int i = 0;i <nums.length;i++) {if(i != 0 && nums[i] == nums[i-1] && !visited[i-1]) { //若發現沒有選擇上一個數，且當前數字與上一個數相同且前一個數沒有被標記過，則可以跳過當前生成的子集。continue;}if(visited[i]) {continue;}visited[i] = true; //做選擇permute.add(nums[i]);backtrack(res, permute, visited, nums);visited[i] = false;//撤銷選擇permute.remove(permute.size() - 1);}}

2.5 (lee-39) 組合總和

給定一個無重復元素的數組 candidates 和一個目標數 target ，找出 candidates 中所有可以使數字和為 target 的組合。
candidates 中的數字可以無限制重復被選取。
所有數字（包括 target）都是正整數。
解集不能包含重復的組合。

輸入：candidates = [2,3,6,7], target = 7,
所求解集為：[ [7], [2,2,3] ]

（1）寫法一

/*** (-------------寫法一 -------------)* [2,3,6,7],7, res = [[7],[2,2,3]]* 思路：畫樹形圖，深度優先遍歷，回溯剪枝* 1.以 target 根結點，創建一個分支時做減;* 2.每一個箭頭表示：從父親結點的數值減去邊上的數值，得到孩子結點的數值。邊的值就是題目中給出的 candidate 數組的每個元素的值;* 3.減到 0 或者負數的時候停止，即：結點 0 和負數結點成為葉子結點;* 4.所有從根結點到結點 0 的路徑（只能從上往下，沒有回路）就是題目要找的一個結果列表。* * 以target=7為例，結果集應該為{{2,2,3},{7}},但是以上步驟會出現重復路徑，比如{2,3,2},{3,2,2}，由于題目不要求順序輸出，因此需要去重，也就是剪枝。* 去重思路：在搜索的過程中去重，每一次搜索的時候設置下一輪搜索的起點start;* * @param candidates* @param target* @return*/public List<List<Integer>> combinationSum(int[] candidates, int target) {List<List<Integer>> res = new ArrayList<>();List<Integer> combinPath = new ArrayList<>();backtrack(res,combinPath,target,candidates,0);return res;}/*** * @param res 結果集* @param combin 從根節點到葉子節點的路徑列表* @param target 每減去一個元素，目標值變小* @param candidates 候選數組* @param start 搜索起點*/private void backtrack(List<List<Integer>> res, List<Integer> combinPath, int target, int[] candidates, int start) {// target 為負數和 0 的時候不再產生新的葉子結點if(target < 0 ) {return;}if(target == 0) {res.add(new ArrayList<>(combinPath));return;}for(int i = start;i < candidates.length;i++) {//從 start 開始搜索combinPath.add(candidates[i]); System.out.println("遞歸之前 => " + combinPath + "，剩余 = " + (target - candidates[i]));backtrack(res, combinPath, target-candidates[i], candidates,i);// 注意：由于每一個元素可以重復使用，下一輪搜索的起點依然是 i，這里非常容易弄錯combinPath.remove(combinPath.size() - 1);System.out.println("遞歸之后 => " + combinPath);}}

（2）寫法二

/*** (-------------寫法二 -------------)* 剪枝提速：如果 target 減去一個數得到負數，那么減去一個更大的樹依然是負數，同樣搜索不到結果;* 基于這個想法，我們可以對輸入數組進行排序，排序是為了提高搜索速度，添加相關邏輯達到進一步剪枝的目的。* 可以打印遞歸前后的輸出查看**** @param candidates* @param target* @return*/public List<List<Integer>> combinationSum1(int[] candidates, int target) {List<List<Integer>> res = new ArrayList<>();List<Integer> combinPath = new ArrayList<>();Arrays.sort(candidates); // 排序是剪枝的前提backtrack1(res,combinPath,candidates,target,0);return res;}private void backtrack1(List<List<Integer>> res, List<Integer> combinPath, int[] candidates, int target, int start) {// 由于進入更深層的時候，小于 0 的部分被剪枝，因此遞歸終止條件值只判斷等于 0 的情況if(target == 0) {res.add(new ArrayList<>(combinPath));return;}for(int i = start ;i < candidates.length;i++) {if(target < candidates[i]) { // 重點理解這里剪枝，前提是候選數組已經有序break;}combinPath.add(candidates[i]);System.out.println("遞歸之前 => " + combinPath + "，剩余 = " + (target - candidates[i]));backtrack1(res, combinPath, candidates, target-candidates[i], i);combinPath.remove(combinPath.size() - 1);System.out.println("遞歸之后 => " + combinPath);}}

2.6 (lee-40) 組合總和2

給定一個數組 candidates 和一個目標數 target ，找出 candidates 中所有可以使數字和為 target 的組合。
candidates 中的每個數字在每個組合中只能使用一次。
說明：
所有數字（包括目標數）都是正整數。
解集不能包含重復的組合。

輸入: candidates = [2,5,2,1,2], target = 5,
輸出: [ [1,2,2], [5] ]

時間復雜度：O(n*2^n)
空間復雜度：O(n)

/*** 思路：畫樹形圖，深度遍歷，剪枝去重* 去重的思路：由于題目要求每個數字在每個組合中只能使用一次并且解集不能包含重復組合，* [2,5,2,1,2] T = 5, res = [[1,2,2],[5]]* @param candidates* @param target* @return*/public List<List<Integer>> combinationSum2(int[] candidates, int target) {List<List<Integer>> res = new ArrayList<>();List<Integer> path = new ArrayList<>();Arrays.sort(candidates); //排序避免重復解backtrack(res,path,candidates,target,0);return res;}/*** * @param res* @param path* @param candidates* @param target* @param start*/private void backtrack(List<List<Integer>> res, List<Integer> path, int[] candidates, int target, int start) {if(target == 0) {res.add(new ArrayList<>(path));return;}for(int i = start;i < candidates.length;i++) { //for循環遍歷從start開始的數，選一個數進入下一層遞歸。 if(target < candidates[i]) { // 剪枝：如果當前candidates數組的和已經大于目標target，沒必要枚舉了，直接returnbreak;}if(i > start && candidates[i] == candidates[i-1]){ //避免子路徑重復，如出現兩個[1,2,2]:如果從start開始的數有連續出現的重復數字，跳過該數字continuecontinue;}path.add(candidates[i]);backtrack(res, path, candidates, target - candidates[i], i+1); //注意為避免一個組合里出現重復使用的情況所以在進入下一層遞歸時要用i+1，從i之后的數中選擇接下來的數，避免出現[1,1,1,1,1]類似這樣path.remove(path.size() - 1); }}

2.7 (lee-93) 復原IP地址

給定一個只包含數字的字符串，用以表示一個 IP 地址，返回所有可能從 s 獲得的有效 IP 地址。你可以按任何順序返回答案。有效 IP 地址正好由四個整數（每個整數位于 0 到 255 之間組成，且不能含有前導 0），整數之間用 ‘.’ 分隔。
例如：“0.1.2.201” 和 “192.168.1.1” 是有效 IP 地址，但是 “0.011.255.245”、“192.168.1.312” 和 “192.168@1.1” 是無效 IP 地址。

輸入：s = “25525511135”
輸出：[“255.255.11.135”,“255.255.111.35”]
輸入：s = “010010”
輸出：[“0.10.0.10”,“0.100.1.0”]

/*** 思路：由于要找出所有可能復原出的 IP 地址，使用回溯的方法，對所有可能的字符串分隔方式進行搜索，并篩選出滿足要求的作為答案。* 回溯套路* @param s* @return*/public List<String> restoreIpAddresses(String s) {List<String> res = new ArrayList<>();List<String> path = new ArrayList<>();backtrack(res,path,s,0);return res;}private void backtrack(List<String> res, List<String> path, String s, int start) {//終止條件if(path.size() > 4) { //IP超過四段終止return;}if(path.size() >= 4 && start != s.length()) { //如果等于4段但不是原字符串也終止return;}if(path.size() == 4) { //如果等于4段并且組合起來是原字符串則添加到結果集里面res.add(String.join(".", path));return;}for(int i = start; i < s.length();i++) {//選擇條件：如果字符串在0-255之外則跳過;如果字符串存在01這種情況也跳過繼續String str = s.substring(start,i+1);if(str.length() > 1 && str.startsWith("0") || str.length() > 3) {continue;} int val = Integer.valueOf(str);if(val < 0 || val > 255) {continue;}path.add(str); //做選擇backtrack(res, path, s, i+1);path.remove(path.size() - 1); //撤銷選擇}}

2.8 (lee-17) 電話號碼的字母組合

給定一個僅包含數字 2-9 的字符串，返回所有它能表示的字母組合。答案可以按任意順序返回。給出數字到字母的映射如下（與電話按鍵相同）。注意 1 不對應任何字母。

輸入：digits = “23”
輸出：[“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”]
輸入：digits = “2”
輸出：[“a”,“b”,“c”]
輸入：digits = “”
輸出：[ ]

public List<String> letterCombinations(String digits) {List<String> res = new ArrayList<>(); if(digits.length() == 0) {return res;}Map<Character,String> map = new HashMap<>();map.put('2', "abc");map.put('3', "def");map.put('4', "ghi");map.put('5', "jkl");map.put('6', "mno");map.put('7', "pqrs");map.put('8', "tuv");map.put('9', "wxyz");backtrack(res,digits,map,new StringBuilder(),0);return res;}/*** * @param res 結果集* @param digits 輸入的String數字串* @param map 存儲字符和字符串的映射* @param cur 當前讀入的內容* @param start */private void backtrack(List<String> res, String digits,Map<Character, String> map, StringBuilder cur ,int start) {if(cur.length() == digits.length()) { //結束條件：當長度夠了就添加結果res.add(cur.toString());return;}char c = digits.charAt(start); //根據當前數字選擇字符String letters = map.get(c);//字符對應的字符串for(int i = 0;i <letters.length();i++) {cur.append(letters.charAt(i));backtrack(res, digits,map, cur ,start+1);cur.deleteCharAt(start);}}

2.9 (lee-131) 分割回文串

給你一個字符串 s，請你將 s 分割成一些子串，使每個子串都是回文串。返回 s 所有可能的分割方案。回文串是正著讀和反著讀都一樣的字符串。

輸入：s = “aab”
輸出：[[“a”,“a”,“b”],[“aa”,“b”]]
輸入：s = “a”
輸出：[[“a”]]

public List<List<String>> partition(String s) {List<List<String>> res = new ArrayList<>();List<String> path = new ArrayList<>();backtrack(res,path,s,0);return res;}/*** 回溯* @param res* @param path* @param s* @param start*/private void backtrack(List<List<String>> res, List<String> path, String s, int start) {if(start == s.length()) { //注意是startres.add(new ArrayList<>(path));return;}for(int i = start;i < s.length();i++) {String str = s.substring(start,i+1);if(!isPalindrome(str)) {continue;}path.add(str);backtrack(res, path, s, i+1); //注意path.remove(path.size() - 1);}}/*** 判斷是否是回文串* @param s* @return*/private boolean isPalindrome(String s) {if(s == null || s.length() <= 1) {return true;}int left = 0;int right = s.length() - 1;while(left < right) {if(s.charAt(left) != s.charAt(right)) {return false;}left++;right--;}return true;}

2.10 (lee-79) 單詞搜索

(lee-JZ12)矩陣中的路徑
請設計一個函數，用來判斷在一個矩陣中是否存在一條包含某字符串所有字符的路徑。路徑可以從矩陣中的任意一格開始，每一步可以在矩陣中向左、右、上、下移動一格。
如果一條路徑經過了矩陣的某一格，那么該路徑不能再次進入該格子。例如，在下面的3×4的矩陣中包含一條字符串“abcced”的路徑（路徑中的字母用加粗標出）。

但矩陣中不包含字符串“abfb”的路徑，因為字符串的第一個字符b占據了矩陣中的第一行第二個格子之后，路徑不能再次進入這個格子。

輸入：board = [[“a”,“b”],[“c”,“d”]], word = “abcd”
輸出：false
輸入：board = [[“A”,“B”,“C”,“E”],[“S”,“F”,“C”,“S”],[“A”,“D”,“E”,“E”]], word = “ABCCED”
輸出：true

/*** dfs + 回溯（重要）*/private int m,n;private int[][] direction = {{1,0},{-1,0},{0,1},{0,-1}};public boolean exist(char[][] board,String word) {m = board.length;n = board[0].length;boolean[][] visited = new boolean[m][n];for(int i = 0;i < m;i++) {for(int j = 0;j < n;j++) {if(dfs(0,i,j,visited,board,word)){return true;}}}return false;}private boolean dfs(int start, int r, int c, boolean[][] visited, char[][] board, String word) {//遞歸結束條件:返回true ---- 字符串以全部匹配if(start == word.length()) { return true;}//遞歸結束條件:返回false ---- 如果行或列索引越界 || 當前矩陣元素與目標字符不同 || 當前矩陣元素已訪問過說明此路不通if(r < 0 || r >= m || c < 0 || c >= n || board[r][c] != word.charAt(start) || visited[r][c]) {return false;}visited[r][c] = true; for(int[] d : direction) {if(dfs(start + 1, r + d[0], c + d[1], visited, board, word)) {return true;}} visited[r][c] = false; return false;}

2.11 (lee-200) 島嶼數量

給你一個由 ‘1’（陸地）和 ‘0’（水）組成的的二維網格，請你計算網格中島嶼的數量。島嶼總是被水包圍，并且每座島嶼只能由水平方向和/或豎直方向上相鄰的陸地連接形成。此外，你可以假設該網格的四條邊均被水包圍。
思路：DFS 通過深度搜索遍歷可能性

輸入：grid = [
[“1”,“1”,“1”,“1”,“0”],
[“1”,“1”,“0”,“1”,“0”],
[“1”,“1”,“0”,“0”,“0”],
[“0”,“0”,“0”,“0”,“0”]
]
輸出：1

public int numIslands(char[][] grid) {if(grid.length==0) {return 0;}int total = 0;int row = grid.length;int col = grid[0].length;for(int i = 0;i < row;i++) {for(int j = 0;j < col;j++) {if(grid[i][j]=='1') {dfs(grid,i,j);total++; }}}return total;}/*** 深度搜索DFS* @param grid 二維網格-島嶼* @param x * @param y* @return*/private void dfs(char[][] grid, int x, int y) {if(x < 0 || x >= grid.length || y < 0 || y >= grid[0].length || grid[x][y] != '1' ) {return;}grid[x][y] = '0';dfs(grid,x-1,y);dfs(grid,x+1,y);dfs(grid,x,y-1);dfs(grid,x,y+1);}

2.12 (lee-JZ13)機器人的運動范圍

地上有一個m行n列的方格，從坐標 [0,0] 到坐標 [m-1,n-1] 。一個機器人從坐標 [0, 0] 的格子開始移動，它每次可以向左、右、上、下移動一格（不能移動到方格外），也不能進入行坐標和列坐標的數位之和大于k的格子。例如，當k為18時，機器人能夠進入方格 [35, 37] ，因為3+5+3+7=18。但它不能進入方格 [35, 38]，因為3+5+3+8=19。請問該機器人能夠到達多少個格子？

輸入：m = 2, n = 3, k = 1
輸出：3
輸入：m = 3, n = 1, k = 0
輸出：1

思路：DFS
首先，我們可以把行坐標和列坐標的數位之和大于k的格子看成是障礙物，標注為1，其他可達的地方標注為0。
其次，因為機器人可以向上下左右移動一格，我們可以將其縮減為向下和向右兩個方向移動，因為當我們從起點向這兩個方向移動時，則新加入的空方格都可以由上方或左方的格子移動一步得到，而且當k值越大，連通的空方格的區域越多。
因此狀態轉移方程可以寫成：visited[i][j] = visited[i-1][j] || visited[i][j-1] visited[i][j]表示可達或者不可達
最后，使用一個變量res來記錄可達的格子的數量
初始條件：visited[i][j] = 0 可達
再說，如何計算數位和？
我們每次將數 X%10 取余的操作得到X的個位數，然后再將X/10，相當于>>一位，刪除個位數，不斷重復直到 X = 0 時結束。
時間復雜度：O(mn) 其中 m 為方格的行數， n 為方格的列數。一共有 O(mn)個狀態需要計算，每個狀態遞推計算的時間復雜度為 O(1)，所以總時間復雜度為 O(mn).
空間復雜度：O(mn) 需要 O(mn)大小的結構來記錄每個位置是否可達。

public class RobotMovingCount { // DFS int res = 0;public int movingCount(int m, int n, int k) {if(k == 0) {return 1;}boolean[][] visited = new boolean[m][n]; //初始化默認為false dfs(visited,0,0,k);return res;}private void dfs(boolean[][] visited, int x, int y, int k) {int m = visited.length;int n = visited[0].length;//越界情況和遇到障礙的情況if(x >= m || x < 0 || y >= n || y < 0 || get(x)+get(y) > k || visited[x][y]) {return ;}visited[x][y] = true; //未遍歷res++;dfs(visited, x+1, y, k); //往下走一格dfs(visited, x, y+1, k); //往右走一格}//位數和private int get(int x) {int res = 0;while(x != 0) {res += x % 10;x /= 10;}return res;}public static void main(String[] args) {Scanner in = new Scanner(System.in);int m = in.nextInt();int n = in.nextInt();int k = in.nextInt();RobotMovingCount rmc = new RobotMovingCount();int res = rmc.movingCount(m, n, k);System.out.print(res);} }

2.13 (lee-JZ38) 字符串的排列

(lee-JZ38)字符串的排列
返回String[]類型：輸入一個字符串，打印出該字符串中字符的所有排列。你可以以任意順序返回這個字符串數組，但里面不能有重復元素。
(NC-JZ27)字符串的排列：返回ArrayList類型。輸入一個字符串,長度不超過9(可能有字符重復),字符只包括大小寫字母。

輸入：s = “abc”
輸出：[“abc”,“acb”,“bac”,“bca”,“cab”,“cba”]

public class Permutation {/** 思路：回溯法* 與lee-46和47類似題目，都是求全排列* 要求不能重復，因此使用47中無重復的排列*/public ArrayList<String> permutation(String s) { ArrayList<String> res = new ArrayList<>();StringBuilder sb = new StringBuilder();Arrays.sort(s.toCharArray()); //按字典序時boolean[] visited = new boolean[s.length()];backtrack(res,sb,visited,s);return res;}private void backtrack(ArrayList<String> res, StringBuilder sb, boolean[] visited, String s) {if(sb.length() == s.length()) {res.add(sb.toString());return;}for(int i = 0;i < visited.length;i++) {if(i != 0 && s.charAt(i)==s.charAt(i-1) && !visited[i-1]) { //若發現沒有選擇上一個字符，且當前字符與上一個字符相同且前一個字符沒有被標記過，則可以跳過當前生成的子集。continue;}if(visited[i]) {continue;}visited[i] = true; //做選擇sb.append(s.charAt(i));backtrack(res, sb, visited, s);visited[i] = false;//撤銷選擇sb.deleteCharAt(sb.length() - 1);}}public static void main(String args[]) {Permutation p = new Permutation();Scanner in = new Scanner(System.in);String s = in.next();ArrayList<String> res = p.permutation(s);System.out.print(res);} }

3 練習鏈接

lee-78 子集
lee-90 子集2
lee-46 全排列
lee-47 全排列2
lee-39 組合總和
lee-40 組合總和2
lee-93 復原IP地址
lee-17 電話號碼的字母組合
lee-131 分割回文串
(lee-79) 單詞搜索
lee-200 島嶼數量
(lee-JZ13)機器人的運動范圍
(lee-JZ38)字符串的排列

總結

以上是生活随笔為你收集整理的回溯（backtrack）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。

backtrack

上一篇：工作总结17：组件封装思想
下一篇：前端学习（2255）代码是如何冲突得