最近幾天在leetcode上刷到排列組合這一類的問題多了起來.
.基本的解決思路就是“回溯算法”，乍一看感覺非常高大上，其實(shí)也就是披著多叉樹遍歷外套的暴力破解法，做多了就會(huì)發(fā)現(xiàn)這就像循環(huán)遍歷數(shù)組一樣，套路固定，故準(zhǔn)備總結(jié)在此，以供交流探討。
2020年9月15日10:04:30
第4次更次博客，今天的leetcode題目是解數(shù)獨(dú)，用回溯法解的非常漂亮，忍不住想分享出來。
2020年9月18日09:42:44
第5次更新，今天的leetcode題目雖然是求排列組合的全排列，但是涉及到去重，還有一個(gè)涉及到去重的問題是，基本思路都是先進(jìn)行排序，然后再做一系列操作。
1 模板
舉個(gè)例子：輸出一串?dāng)?shù)字[1,2,3]的全排列[1,2,3]，[1,3,2]，[2,1,3]，[2,3,1]，[3,1,2]，[3,2,1]。
這個(gè)問題交給人類來解決的話肯定是先固定第一位為 1，然后第二位可以是 2，那么第三位只能是 3；然后可以把第二位變成 3，第三位就只能是 2 了；然后就只能變化第一位，變成 2，然后再窮舉后兩位，以此類推......
就像下面這樣的一個(gè)樹形結(jié)構(gòu)：
當(dāng)我們停留在每一個(gè) 節(jié)點(diǎn)上時(shí)，都需要做一個(gè)決策，例如停留在圖中紅色節(jié)點(diǎn)上時(shí)，有[1, 3]兩個(gè)數(shù)字可以做選擇，如果選擇了1之后再選擇數(shù)字3（最后一個(gè)數(shù)字只有一個(gè)選項(xiàng)），則已經(jīng)找到了一個(gè)不重復(fù)的數(shù)字，這一次的選擇就結(jié)束了，我們會(huì)退回紅色的節(jié)點(diǎn)繼續(xù)向右子樹搜索，以此類推......直到找到左右的結(jié)果。
這其實(shí)就是回溯算法，中學(xué)的時(shí)候就已經(jīng)不自覺地掌握了。我們可以抽象一點(diǎn)，把整個(gè)算法的解決模板給概括出來，即：
解決一個(gè)回溯問題，實(shí)際上就是一個(gè)決策樹的遍歷過程，確定了以下三個(gè)條件，問題就迎刃而解了：
- 路徑：已經(jīng)做出的選擇
- 選擇列表：當(dāng)前可以做的選擇
- 結(jié)束條件（遞歸出口）：到達(dá)決策的底層，沒有選擇可做的條件
偽代碼如下：
List<T> result = new ArrayList<>();
private void backtrack(路徑, 選擇列表){
if(滿足結(jié)束條件){
result.add(路徑);
return;
}
for(選擇 : 選擇列表){
做選擇;
backtrack(路徑, 選擇列表);
撤銷選擇;
}
}
上面藍(lán)色文字“決策”對(duì)應(yīng)的就是代碼中的“做選擇”，“結(jié)束”對(duì)應(yīng)“滿足結(jié)束條件”，“退回”對(duì)應(yīng)“撤銷選擇”
其核心就是 for 循環(huán)里面的遞歸，在遞歸調(diào)用之前「做選擇」，在遞歸調(diào)用之后「撤銷選擇」，特別簡(jiǎn)單。
多說無益，上例子。
2 排列組合問題
2.1 leetcode 77 組合
評(píng)論區(qū)里面的圖畫的已經(jīng)非常直觀了，我這里直接引用一下
根據(jù)我上面給的三個(gè)條件，將其對(duì)應(yīng)在本題中如下：
- 路徑：就是圖中紅色方塊部分，當(dāng)然樹干上面“取X”也是路徑
- 選擇列表：就是圖中藍(lán)色方塊部分
- 結(jié)束條件：路徑中包含k個(gè)數(shù)字時(shí)。
我們定義的函數(shù)其實(shí)就像是一個(gè)指針，將這棵樹的所有節(jié)點(diǎn)都走一遍之后整個(gè)程序就執(zhí)行完畢了，所得的結(jié)果就是正確結(jié)果。如何將這棵樹所有的節(jié)點(diǎn)都走一遍？其實(shí)就是前序遍歷，中序遍歷，后序遍歷：
private traverse(TreeNode root){
for(TreeNode child : root.children){
traverse(child);
}
}
我們做選擇以及撤銷選擇的動(dòng)作正是在前序和后序的時(shí)間點(diǎn)做出的，即做了一個(gè)選擇之后到下一個(gè)節(jié)點(diǎn)，將做的選擇撤銷以后回到上一個(gè)節(jié)點(diǎn)！
所以回溯算法的核心框架：
for(選擇 : 選擇列表){
// 做選擇
將被選的項(xiàng)從候選表中刪除;
路徑.add(選擇);
backtrack(路徑, 選擇列表);
// 撤銷選擇
路徑.remove(選擇);
重新將被選的項(xiàng)加入候選表;
}
我們只要在遞歸之前做出選擇，在遞歸之后撤銷剛才的選擇，就能正確得到每個(gè)節(jié)點(diǎn)的選擇列表和路徑。
本題解決方案如下：
class Solution {
private List<List<Integer>> result = new ArrayList<>();
// 用一個(gè)棧來記錄每一個(gè)組合
private void findCombinations(int n, int k, int begin, Stack<Integer> pre){
if(pre.size() == k){
result.add(new ArrayList<>(pre));
return;
}
for(int i = begin; i <= n; i ++){
pre.push(i);
findCombinations(n, k, i + 1, pre); // 從下一個(gè)數(shù)字開始取
// 當(dāng)前數(shù)字的情況已經(jīng)全部取完，彈出棧頂元素
pre.pop();
}
}
public List<List<Integer>> combine(int n, int k) {
if (n <= 0 || k <= 0 || n < k) {
return result;
}
findCombinations(n, k, 1, new Stack<>());
return result;
}
}
這一部分就是遞歸出口（可以結(jié)合題意理解，我們只要找到k個(gè)數(shù)字就好）
每一個(gè)數(shù)字 i 就是要做的選擇
返回用一個(gè)List來存儲(chǔ)（當(dāng)然其他的數(shù)據(jù)結(jié)構(gòu)都可以~）
?撤銷選擇操作，其實(shí)就是做選擇的逆動(dòng)作
?
2.2?leetcode 216 組合總和III
找出所有相加之和為?n 的?k?個(gè)數(shù)的組合。組合中只允許含有 1 -?9 的正整數(shù)，并且每種組合中不存在重復(fù)的數(shù)字。
示例 1:
輸入: k = 3, n = 7
輸出: [[1,2,4]]
這種找出總和為某數(shù)字的問題，套路也很固定，只需在回溯函數(shù)里多添加一個(gè)遍歷target用于記錄求和的目標(biāo)是多少即可。
class Solution {
private List<List<Integer>> result = new ArrayList<>();
private List<Integer> temp = new ArrayList<>();
public List<List<Integer>> combinationSum3(int k, int n) {
dfs(k, n, 1);
return result;
}
private void dfs(int k, int sum, int start){
if(k == 0 && sum == 0){ // 符合條件
result.add(new ArrayList<>(temp)); // 注意深拷貝和淺拷貝！！必須是new一個(gè)新數(shù)組
return;
}
if(k == 0 || sum < 0) return; // 不符合條件
for(int i = start; i <= 9; i ++){
temp.add(i);
dfs(k - 1, sum - i, i + 1);
temp.remove(temp.size() - 1); // 回溯
}
return;
}
}
2.3?leetcode 60 組合總和III
給出集合?[1,2,3,…,n]，其所有元素共有?n! 種排列。
按大小順序列出所有排列情況，并一一標(biāo)記，當(dāng)?n = 3 時(shí), 所有排列如下：
? ? ?"123"
? ? ?"132"
? ? ?"213"
? ? ?"231"
? ? ?"312"
? ? ?"321"
給定?n 和?k，返回第?k?個(gè)排列。
leetcode上面的一個(gè)題解很優(yōu)秀，這里引用一下。?
public String getPermutation(int n, int k) {
int[] nums = new int[n];//生成nums數(shù)組
for (int i = 0; i < n; i++){
nums[i] = i + 1;
}
boolean[] used = new boolean[n];//記錄當(dāng)前的索引的數(shù)是否被使用過
return dfs(nums, new ArrayList<String>(), used, 0, n, k);
}
/**
* @param nums 源數(shù)組
* @param levelList 每一層的選擇
* @param used 數(shù)組的元素是否被使用過
* @param depth 深度，也就是當(dāng)前使用的元素的索引
* @param n 上限值
* @param k 第k個(gè)
* @return 第k個(gè)排列
*/
private String dfs(int[] nums, List<String> levelList, boolean[] used, int depth, int n, int k) {
if (depth == n) {//觸發(fā)出口條件，開始收集結(jié)果集
StringBuilder res = new StringBuilder();
for (String s : levelList){
res.append(s);
}
return res.toString();
}
int cur = factorial(n - depth - 1);//當(dāng)前的depth也就是索引，有多少排列數(shù)
for (int i = 0; i < n; i++) {
if (used[i]) continue;//當(dāng)前元素被使用過，做剪枝
if (cur < k) {//當(dāng)前的排列組合數(shù)小于k，說明就算這一層排完了，也到不了第k個(gè)，剪枝
k -= cur;
continue;
}
levelList.add(nums[i] + "");//list收的是string類型
used[i] = true;//當(dāng)前元素被使用過標(biāo)記
return dfs(nums, levelList, used, depth + 1, n, k);
}
return null;
}
//返回n的階乘，如3!=3*2*1=6
private int factorial(int n) {
int res = 1;
while (n > 0) {
res *= n--;
}
return res;
}
2.4 全排列II
給定一個(gè)可包含重復(fù)數(shù)字的序列，返回所有不重復(fù)的全排列。
涉及到去重的問題，一般思路都是將候選數(shù)組進(jìn)行排序，然后再做一系列操作。這里我們選擇對(duì)原數(shù)組排序，保證相同的數(shù)字都相鄰，然后每次填入的數(shù)一定是這個(gè)數(shù)所在重復(fù)數(shù)集合中「從左往右第一個(gè)未被填過的數(shù)字」，即如下的判斷條件：
if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
continue;
}
詳細(xì)代碼如下：
class Solution {
private boolean[] used;
private List<List<Integer>> result;
public List<List<Integer>> permuteUnique(int[] nums) {
used = new boolean[nums.length];
result = new ArrayList<>();
Arrays.sort(nums);
backtrack(nums, new ArrayList<>(), 0);
return result;
}
private void backtrack(int[] nums, List<Integer> path, int index){
if(index >= nums.length){
result.add(new ArrayList<Integer>(path));
return;
}
for(int i = 0; i < nums.length; i ++){
if(used[i]){
continue;
}
// 只使用重復(fù)數(shù)字的第一個(gè)
// !used[i - 1] 說明當(dāng)前重復(fù)數(shù)字左邊還有未使用過的
if(i > 0 && nums[i] == nums[i - 1] && !used[i - 1]){
continue;
}
path.add(nums[i]);
used[i] = true;
backtrack(nums, path, index + 1);
// 回溯
used[i] = false;
path.remove(path.size() - 1);
}
}
}
3 子序列問題
?當(dāng)然排列組合問題當(dāng)然不僅限于全排列問題，還有可能讓我們從候選項(xiàng)中選出一些元素出來，就是所謂的求子序列。
leetcode 1079 活字印刷
你有一套活字字模?tiles，其中每個(gè)字模上都刻有一個(gè)字母?tiles[i]。返回你可以印出的非空字母序列的數(shù)目。
注意：本題中，每個(gè)活字字模只能使用一次。
示例 1：
輸入："AAB"
輸出：8
解釋：可能的序列為 "A", "B", "AA", "AB", "BA", "AAB", "ABA", "BAA"。
同樣是明確三個(gè)條件：
- 路徑：同上題，先前已經(jīng)選擇的字母組成的字符串。
- 選擇列表：剩下可供選擇的字母，即 title 中除了被用掉的字母之外的所有字母
- 結(jié)束條件：由于每一個(gè)結(jié)果的長(zhǎng)度不是固定的，而且我們只需要統(tǒng)計(jì)個(gè)數(shù)，所以在生成"AA"的途中我們必然會(huì)經(jīng)過"A"，這是計(jì)數(shù)器也要進(jìn)行累加。
這個(gè)題目算是比較特殊的，只用統(tǒng)計(jì)最后子序列的個(gè)數(shù)，所以在遞歸調(diào)用時(shí)不需要再傳入路徑和選擇列表，不過在分析問題的時(shí)候還是要明確這兩個(gè)概念，這樣才不至于代碼出錯(cuò)。
參考代碼：
class Solution {
int result = 0;
public int numTilePossibilities(String tiles) {
char[] counter = new char[26];
for(int i = 0; i < tiles.length(); i ++){
counter[tiles.charAt(i) - 'A'] ++;
}
backtrack(counter);
return result;
}
private void backtrack(char[] counter){
for(int i = 0; i < 26; i ++){
// 剪枝，即排除無效選擇
if(counter[i] == 0) continue;
// 進(jìn)行一次具體選擇，本題就是 i 計(jì)數(shù)器減 1
counter[i] --;
// 一次有效枚舉，總的計(jì)數(shù)器加 1
result ++;
// 繼續(xù)回溯：遞歸 + 選擇（盡可能剪枝） + 回退之前的現(xiàn)場(chǎng)恢復(fù)
backtrack(counter);
// 回退之前，也就是進(jìn)入另一分支之前，恢復(fù)當(dāng)前分支的改動(dòng)
counter[i] ++;
}
}
}
由于并不需要輸出最后得結(jié)果，所以只用將每個(gè)字母出現(xiàn)的頻率統(tǒng)計(jì)出來就好（所幸英文字母的數(shù)量是可數(shù)的）。
一個(gè)選擇就是選了一個(gè)字母，相應(yīng)的頻率減一就ok。
撤銷選擇就是將剛剛選擇的字母重新放回候選列表中，即相應(yīng)的字母頻率加一。
4 子序列問題2
上面的問題其實(shí)是討巧的，英文單詞個(gè)數(shù)只有26個(gè)，并且只用輸出序列的個(gè)數(shù)就可以了。如果將字母換做數(shù)字，那么就還是要老老實(shí)實(shí)地按照回溯的流程去做。
leetcode 面試題 08.04 冪集
冪集。編寫一種方法，返回某集合的所有子集。集合中不包含重復(fù)的元素。
說明：解集不能包含重復(fù)的子集。
分析的三個(gè)條件和上題類似，只不過是將字母變作數(shù)字。
由于是子序列，所以我們?cè)趶?0 到 length - 1 遍歷候選數(shù)組時(shí)有一些數(shù)字是可以不選的，因此就會(huì)在遞歸調(diào)用時(shí)產(chǎn)生分叉，只需多考慮一種情況即可。
class Solution {
List<List<Integer>> result = new ArrayList<>();
List<Integer> temp = new ArrayList<>();
public List<List<Integer>> subsets(int[] nums) {
dfs(nums, 0);
return result;
}
private void dfs(int[] nums, int index){
if(index >= nums.length){
result.add(new ArrayList<>(temp)); // 注意淺拷貝
return;
}
// 不選擇當(dāng)前數(shù)字
dfs(nums, index + 1);
// 選擇當(dāng)前數(shù)字
temp.add(nums[index]);
dfs(nums, index + 1);
// 回溯
temp.remove(temp.size() - 1);
}
}
當(dāng)遍歷數(shù)組的索引值超出數(shù)組范圍時(shí)就是返回條件：
有兩種情況需要考慮：選擇當(dāng)前數(shù)字 / 不選當(dāng)前數(shù)字?：
如果選擇了當(dāng)前數(shù)字的話就需要在結(jié)果集temp中進(jìn)行添加
撤銷選擇操作就是將剛剛選擇的數(shù)字從路徑中刪除即可：?
5 24點(diǎn)游戲
leetcode 679 24點(diǎn)游戲
一共有 4 個(gè)數(shù)和 3 個(gè)運(yùn)算操作，因此可能性非常有限。一共有多少種可能性呢？
首先從 4 個(gè)數(shù)字中有序地選出 2 個(gè)數(shù)字，共有 4×3=12 種選法，并選擇加、減、乘、除 4 種運(yùn)算操作之一，用得到的結(jié)果取代選出的 2 個(gè)數(shù)字，剩下 3 個(gè)數(shù)字。
實(shí)現(xiàn)時(shí)，有一些細(xì)節(jié)需要注意。
- 除法運(yùn)算為實(shí)數(shù)除法，因此結(jié)果為浮點(diǎn)數(shù)，列表中存儲(chǔ)的數(shù)字也都是浮點(diǎn)數(shù)。在判斷結(jié)果是否等于 24 時(shí)應(yīng)考慮精度誤差，這道題中，誤差小于 10^{-6}可以認(rèn)為是相等。
- 進(jìn)行除法運(yùn)算時(shí)，除數(shù)不能為 0，如果遇到除數(shù)為 0 的情況，則這種可能性可以直接排除。由于列表中存儲(chǔ)的數(shù)字是浮點(diǎn)數(shù)，因此判斷除數(shù)是否為 0 時(shí)應(yīng)考慮精度誤差，這道題中，當(dāng)一個(gè)數(shù)字的絕對(duì)值小于 10^{-6}時(shí)，可以認(rèn)為該數(shù)字等于 0。
一共有 4 個(gè)數(shù)和 3 個(gè)運(yùn)算操作，因此可能性非常有限。
首先從 4 個(gè)數(shù)字中有序地選出 2 個(gè)數(shù)字，共有 4×3=12 種選法，并選擇加、減、乘、除 4 種運(yùn)算操作之一，用得到的結(jié)果取代選出的 2 個(gè)數(shù)字，剩下 3 個(gè)數(shù)字。
實(shí)現(xiàn)時(shí)，有一些細(xì)節(jié)需要注意。
- 除法運(yùn)算為實(shí)數(shù)除法，因此結(jié)果為浮點(diǎn)數(shù)，列表中存儲(chǔ)的數(shù)字也都是浮點(diǎn)數(shù)。在判斷結(jié)果是否等于 24 時(shí)應(yīng)考慮精度誤差，這道題中，誤差小于 10^{-6}可以認(rèn)為是相等。
- 進(jìn)行除法運(yùn)算時(shí)，除數(shù)不能為 0，如果遇到除數(shù)為 0 的情況，則這種可能性可以直接排除。由于列表中存儲(chǔ)的數(shù)字是浮點(diǎn)數(shù)，因此判斷除數(shù)是否為 0 時(shí)應(yīng)考慮精度誤差，這道題中，當(dāng)一個(gè)數(shù)字的絕對(duì)值小于 10^{-6}時(shí)，可以認(rèn)為該數(shù)字等于 0。
class Solution {
static final int ADD = 0, MULTIPLY = 1, SUBTRACT = 2, DIVIDE = 3;
public boolean judgePoint24(int[] nums) {
List<Double> list = new ArrayList<Double>();
for (int num : nums) {
list.add((double) num);
}
return backtrack(list);
}
public boolean backtrack(List<Double> list) {
if (list.size() == 0) {
return false;
}
if (list.size() == 1) {
return Math.abs(list.get(0) - 24) < 1e-6;
}
int size = list.size();
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
if (i != j) { // 選出來i，j這兩個(gè)位置的數(shù)字做四則運(yùn)算
List<Double> list2 = new ArrayList<Double>();
for (int k = 0; k < size; k++) {
if (k != i && k != j) { // 剩下的數(shù)字保持不變
list2.add(list.get(k));
}
}
for (int k = 0; k < 4; k++) {
if (k == ADD) { // 加法
list2.add(list.get(i) + list.get(j));
} else if (k == MULTIPLY) { // 乘法
list2.add(list.get(i) * list.get(j));
} else if (k == SUBTRACT) { // 減法
list2.add(list.get(i) - list.get(j));
} else if (k == DIVIDE) { // 除法
if (Math.abs(list.get(j)) < 1e-6) { // 分母不能為0
continue;
} else {
list2.add(list.get(i) / list.get(j));
}
}
if (backtrack(list2)) {
return true;
}
// 回溯
list2.remove(list2.size() - 1);
}
}
}
}
return false;
}
}
6 N皇后問題（放置問題）?
決策樹的每一層表示棋盤的每一行，每個(gè)節(jié)點(diǎn)可以做的選擇是在該行任意位置放置一個(gè)皇后。
路徑：board，其中小于row的那些行都已經(jīng)選好了放皇后的位置
? ? ? ?選擇列表：第row行的每一個(gè)位置
? ? ? ?返回條件：row超出borad范圍
class Solution {
private List<List<String>> res = new ArrayList<>();
public List<List<String>> solveNQueens(int n) {
List<String> board = new ArrayList<>();
for(int i = 0; i < n; i ++){
String temp = "";
for(int j = 0; j < n ; j ++){
temp += '.';
}
board.add(temp);
}
backtrack(board, 0);
return res;
}
// 路徑：board，其中小于row的那些行都已經(jīng)選好了放皇后的位置
// 選擇列表：第row行的每一個(gè)位置
// 返回條件：row超出borad范圍
private void backtrack(List<String> board, int row){
if(row == board.size()){
res.add(new ArrayList<>(board));
return;
}
int n = board.get(row).length();
for(int col = 0; col < n; col ++){
if(!valid(board, row, col)){
continue;
}
char[] str = board.get(row).toCharArray();
// 做選擇
str[col] = 'Q';
board.set(row, new String(str));
// 回溯
backtrack(board, row + 1);
// 撤銷選擇
str[col] = '.';
board.set(row, new String(str));
}
}
// 是否可以在該位置放置
private boolean valid(List<String> board, int row, int col){
int n = board.get(row).length();
// 檢查列
for(int i = 0; i < n; i ++){
if(board.get(i).charAt(col) == 'Q'){
return false;
}
}
// 檢查右上方
for(int i = row - 1, j = col + 1; i >= 0 && j < n; i --, j ++){
if(board.get(i).charAt(j) == 'Q'){
return false;
}
}
// 檢查左上方
for(int i = row - 1, j = col - 1; i >=0 && j >= 0; i --, j --){
if(board.get(i).charAt(j) == 'Q'){
return false;
}
}
return true;
}
}
7?搜索所有可行解
7.1 leetcode 39 組合總和
給定一個(gè)無重復(fù)元素的數(shù)組?candidates?和一個(gè)目標(biāo)數(shù)?target?，找出?candidates?中所有可以使數(shù)字和為?target?的組合。
candidates?中的數(shù)字可以無限制重復(fù)被選取。
說明：
所有數(shù)字（包括?target）都是正整數(shù)。
解集不能包含重復(fù)的組合。?
定義遞歸函數(shù) backtrack(int[] candidates, int target, List<Integer> path, int startIndex) 表示當(dāng)前在 candidates 數(shù)組的第 startIndex?位，還剩 target 要組合，已經(jīng)組合的列表為 path。
遞歸的終止條件為 target <= 0 或者 candidates 數(shù)組被全部用完。那么在當(dāng)前的函數(shù)中，每次我們可以選擇跳過不用第 startIndex?個(gè)數(shù)，即執(zhí)行 backtrack(candidates,?target, path, startIndex + 1)。也可以選擇使用第 startIndex個(gè)數(shù)，即執(zhí)行 dfs(candidates,?target - candidates[startIndex ], combine, startIndex ).
注意到每個(gè)數(shù)字可以被無限制重復(fù)選取，因此搜索的下標(biāo)仍為 startIndex 。
class Solution {
List<List<Integer>> result = new ArrayList<>();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<Integer> path = new ArrayList<>();
backtrack(candidates, target, path, 0);
return result;
}
private void backtrack(int[] candidates, int target, List<Integer> path, int startIndex){
if(startIndex == candidates.length){
return;
}
if(target == 0){
result.add(new ArrayList<Integer>(path));
return;
}
// 不選當(dāng)前數(shù)字
backtrack(candidates, target, path, startIndex + 1);
// 選當(dāng)前數(shù)字
if(target >= candidates[startIndex]){
path.add(candidates[startIndex]);
// 每個(gè)數(shù)字可以被無限制重復(fù)選取，因此搜索的下標(biāo)仍為 startIndex
backtrack(candidates, target - candidates[startIndex], path, startIndex);
// 回溯
path.remove(path.size() - 1);
}
}
}
7.2 組合總和II
給定一個(gè)數(shù)組?candidates?和一個(gè)目標(biāo)數(shù)?target?，找出?candidates?中所有可以使數(shù)字和為?target?的組合。
candidates?中的每個(gè)數(shù)字在每個(gè)組合中只能使用一次。
和上面的題目框架是類似的，只不過上題要求數(shù)字可以無限次使用，本題要求數(shù)字只能被用一次，所以需要去重操作，一個(gè)簡(jiǎn)單的去重思路是將數(shù)組進(jìn)行從小到大排序，當(dāng)后面一個(gè)數(shù)字等于前面一個(gè)數(shù)字時(shí)直接continue。其余框架不變。
class Solution {
List<List<Integer>> result = new ArrayList<>();
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
List<Integer> path = new ArrayList<>();
Arrays.sort(candidates);
backtrack(candidates, target, path, 0);
return result;
}
private void backtrack(int[] candidates, int target, List<Integer> path, int startIndex){
if(target == 0){
result.add(new ArrayList<Integer>(path));
return;
}
for(int i = startIndex; i < candidates.length; i ++){
if(candidates[i] > target){
break;
}
// 保證不重復(fù)
if(i > startIndex && candidates[i] == candidates[i-1]){
continue;
}
path.add(candidates[i]);
backtrack(candidates, target - candidates[i], path, i + 1);
path.remove(path.size() - 1);
}
}
}
8?回溯和圖的遍歷結(jié)合
leetcode 79?單次搜索
給定一個(gè)二維網(wǎng)格和一個(gè)單詞，找出該單詞是否存在于網(wǎng)格中。
單詞必須按照字母順序，通過相鄰的單元格內(nèi)的字母構(gòu)成，其中“相鄰”單元格是那些水平相鄰或垂直相鄰的單元格。同一個(gè)單元格內(nèi)的字母不允許被重復(fù)使用。
設(shè)函數(shù)check(i,j,k) 判斷以網(wǎng)格的 (i, j) 位置出發(fā)，能否搜索到單詞 word[k..]
路徑：當(dāng)前匹配到的位置k
返回條件：k移動(dòng)到word尾或者i，j超出二維數(shù)組邊界
class Solution {
public boolean exist(char[][] board, String word) {
for (int i = 0; i < board.length; ++i) {
for (int j = 0; j < board[i].length; ++j) {
if (board[i][j] == word.charAt(0)) {
if (backtrack(board, word, i, j, 0)) return true;
}
}
}
return false;
}
private boolean backtrack(char[][] board, String word, int i, int j, int k){
if (k == word.length()) {
return true;
}
if (i < 0 || j < 0 || i >= board.length || j >= board[i].length) {
return false;
}
if (word.charAt(k) != board[i][j]) {
return false;
}
// 匹配當(dāng)前位置
char t = board[i][j];
board[i][j] = '0';
boolean res = backtrack(board, word, i + 1, j, k + 1) ||
backtrack(board, word, i - 1, j, k + 1) ||
backtrack(board, word, i, j + 1, k + 1) ||
backtrack(board, word, i, j - 1, k + 1);
// 回溯
board[i][j] = t;
return res;
}
}
9 求解數(shù)獨(dú)
求解數(shù)獨(dú)的思路就是對(duì)每一個(gè)格子所有可能的數(shù)字1-9進(jìn)行窮舉，基于此，我們可以寫出代碼框架：
public void solveSudoku(char[][] board) {
backtrack(board, 0, 0);
}
// 從左上角(r,c)開始回溯求解數(shù)組
public void backtrack(char[][] board, int r, int c){
int m = 9;
int n = 9;
// 對(duì)棋盤的每個(gè)位置進(jìn)行窮舉
for (int i = r; i < m; i++) {
for (int j = c; j < n; j++) {
for (char ch = '1'; ch <= '9'; ch ++) {
// 做選擇
board[i][j] = ch;
// 繼續(xù)窮舉下一個(gè)
backtrack(board, i, j + 1);
// 撤銷選擇
board[i][j] = '.';
}
}
}
}
如果?j?到最后一列了我們應(yīng)該從下一行開始繼續(xù)，如果 i 到最后一行了我們就等于窮舉完了所有情況，返回即可。為了減少?gòu)?fù)雜度，我們可以讓backtrack函數(shù)返回值為boolean，如果找到一個(gè)可行解就返回 true，這樣就可以阻止后續(xù)的遞歸。
class Solution {
public void solveSudoku(char[][] board) {
backtrack(board, 0, 0);
}
// 從左上角(r,c)開始回溯求解數(shù)組
public boolean backtrack(char[][] board, int r, int c){
int m = 9;
int n = 9;
if(c == n){
// 到最后一列則從下一行開始
return backtrack(board, r + 1, 0);
}
if(r == m){
return true;
}
// 對(duì)每個(gè)位置窮舉
for(int i = r; i < m; i ++){
for(int j = c; j < n; j ++){
// 此處已經(jīng)有數(shù)字
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] = '.';
}
// 窮舉完仍沒找到
return false;
}
}
return false;
}
public boolean isValid(char[][] board, int r, int c, char ch){
for(int i = 0; i < 9; i ++){
// 判斷行是否有重復(fù)數(shù)字
if(board[r][i] == ch){
return false;
}
// 判斷列是否有重復(fù)數(shù)字
if(board[i][c] == ch){
return false;
}
// 判斷3×3區(qū)域內(nèi)是否有重復(fù)數(shù)字
if(board[(r/3)*3 + i/3][(c/3)*3 + i%3] == ch){
return false;
}
}
return true;
}
}
10 總結(jié)
回溯算法就是個(gè)多叉樹的遍歷問題，關(guān)鍵就是在前序遍歷和后序遍歷的位置做一些操作。
寫回溯函數(shù)時(shí)，需要維護(hù)走過的路徑和當(dāng)前可以做的選擇列表，當(dāng)滿足結(jié)束條件時(shí)，將路徑記入結(jié)果集。
