第七章 回溯算法part01
理論基礎(chǔ)
重點(diǎn)摘錄
- 回溯法解決的問題都可以抽象為樹形結(jié)構(gòu)，是的，我指的是所有回溯法的問題都可以抽象為樹形結(jié)構(gòu)！
- 因?yàn)榛厮莘ń鉀Q的都是在集合中遞歸查找子集，集合的大小就構(gòu)成了樹的寬度，遞歸的深度就構(gòu)成了樹的深度。
- 遞歸就要有終止條件，所以必然是一棵高度有限的樹（N叉樹）。
回溯法模板
- 返回值和參數(shù)：返回值一般是void，參數(shù)一般是寫完邏輯再確定
- 終止條件：看題意決定，一般是找到了符合條件的葉子節(jié)點(diǎn)。
回溯法模板偽代碼：
void backtracking(參數(shù)) {
if (終止條件) {
存放結(jié)果;
return;
}
for (選擇：本層集合中元素（樹中節(jié)點(diǎn)孩子的數(shù)量就是集合的大?。? {
處理節(jié)點(diǎn);
backtracking(路徑，選擇列表); // 遞歸
回溯，撤銷處理結(jié)果
}
}
77. 組合
- 對(duì)著 在 回溯算法理論基礎(chǔ) 給出的 代碼模板，來做本題組合問題，大家就會(huì)發(fā)現(xiàn) 寫回溯算法套路。
- 本題關(guān)于剪枝操作是大家要理解的重點(diǎn)，因?yàn)楹竺婧芏嗷厮菟惴ń鉀Q的題目，都是這個(gè)剪枝套路。
思路
- 組合不強(qiáng)調(diào)順序，排列強(qiáng)調(diào)順序。
- 暴力解法就是有多少k就要嵌套多少for循環(huán)?；厮菟惴ū举|(zhì)上也是窮舉，但是通過遞歸有多少for循環(huán)。
-
回溯算法搜素的過程：
示例
偽代碼實(shí)現(xiàn)：
// 一個(gè)組合就是一個(gè)一維數(shù)組，結(jié)果集就是一個(gè)二維數(shù)組
// 用來存放符合條件結(jié)果
private List<Integer> path = new ArrayList<>();
// 存放符合條件結(jié)果的集合
private List<List<Integer>> result = new ArrayList<>();
//遞歸的參數(shù)及返回值
//startIndex 每次搜索的起始位置，初始位置是1
private void backtracking(int n, int k, int startIndex){
//確定終止條件：到葉子節(jié)點(diǎn)
if(path.size() == k){
result.add(new ArrayList<>(path));
return;
}
//單層遞歸的邏輯：每一個(gè)節(jié)點(diǎn)都是for循環(huán)
for(i=startIndex; i<=n; i++){
path.add(i);
backtracking(n, k, i+1);
path.remove(path.size() - 1); //比如，12之后是13，要把2彈出，把3加進(jìn)來，才能得到13
}
}
這道題還可以做剪枝
比如n=4，k=4，在{2,x,x,x}的分支下，一共只剩下3個(gè)元素（234），怎么也不可能出現(xiàn)k=4的情況，所以就可以做剪枝，{3,x,x,x}（只剩下元素34），{4,x,x,x}（只剩下元素4）也是一樣的。
原來的代碼
private void backtracking(int n, int k, int startIndex){
……
//單層邏輯
for(i=startIndex; i<=n; i++){
path.add(i);
backtracking(n, k, i+1); //遞歸可以理解為，沿著節(jié)點(diǎn)的樹形結(jié)構(gòu)往下搜索的過程。i可以理解為每個(gè)節(jié)點(diǎn)的子孩子。我們要剪枝的就是一些節(jié)點(diǎn)的子孩子。
path.remove(path.size() - 1);
}
path可以理解為要選擇的元素，k-path.size()
就是還需要選取的元素的個(gè)數(shù)。還需要選取的元素個(gè)數(shù)，至多開始的位置=(k-path.size()) + 1，+1是因?yàn)橐鹗嘉恢?/p>
class Solution {
private List<Integer> path = new ArrayList<>();
private List<List<Integer>> result = new ArrayList<>();
private void backtracking(int n, int k, int startIndex){
if(path.size() == k){
result.add(new ArrayList<>(path));
return;
}
for(int i = startIndex; i <= n - (k-path.size()) +1; i++){
path.add(i);
backtracking(n, k, i+1);
path.remove(path.size()-1);
}
}
public List<List<Integer>> combine(int n, int k) {
result.clear();
path.clear();
backtracking(n, k, 1);
return result;
}
}
216.組合總和III
思路
- 回溯算法，for循環(huán)里嵌套回溯算法，用遞歸的方式實(shí)現(xiàn)。
-
抽象成樹形結(jié)構(gòu)（任何回溯算法都可以抽象為樹形結(jié)構(gòu)）。
來源：代碼隨想錄
偽代碼
path（一維數(shù)組）
result（二維數(shù)組）
void backtracking(int targetSum, int k, int sum, int startIndex){
if(sum > targetSum) return; //剪枝1
//終止條件
if(path.size() == k){
if(targetSum == sum) result.add(new ArrayList<>(path));
return;
}
//單層搜索邏輯
//for(int i = startIndex; i <= 9; i++){ //可以剪枝
for(int i = startIndex; i <= 9-(k-path.size())+1; i++){
sum += i;
path.add(i);
backtracking(targetSum, k, sum, i + 1);
sum -= i;
path.remove(path.size()-1);
}
}
class Solution {
private List<List<Integer>> result = new ArrayList<>();
private List<Integer> path = new ArrayList<>();
private void backtracking(int sum, int k, int targetSum, int startIndex){
if(sum > targetSum) return;
if(path.size() == k){
if(sum == targetSum) result.add(new ArrayList<>(path));
return;
}
for(int i = startIndex; i <= 9 - (k - path.size()) + 1; i++){ //注意這里是<=
sum += i;
path.add(i);
backtracking(sum, k, targetSum, i+1);
sum -= i;
//path.remove(path.size()-1); 可以用下面這個(gè)方法
path.removeLast();
}
}
public List<List<Integer>> combinationSum3(int k, int n) {
result.clear();
path.clear();
backtracking(0, k, n, 1);
return result;
}
}
17.電話號(hào)碼的字母組合
題目鏈接/文章講解
本題大家剛開始做會(huì)有點(diǎn)難度，先自己思考20min，沒思路就直接看題解。
思路
- 使用map或者二維數(shù)組做映射
private static final String[] letterMap = {
"", // 0
"", // 1
"abc", // 2
"def", // 3
"ghi", // 4
"jkl", // 5
"mno", // 6
"pqrs",// 7
"tuv", // 8
"wxyz" // 9
};
圖示
樹的深度：輸入數(shù)字的個(gè)數(shù)
樹的寬度：每個(gè)數(shù)字對(duì)應(yīng)的字母
cr：代碼隨想錄
偽代碼
private List<String> result = new ArrayList<>();
private StringBuilder s = new StringBuilder();
private void backtracking(String digits, int index) { //index 是遞歸中傳入的字符串遍歷到哪一個(gè)數(shù)字了
if(index == digits.length()){
result.add(s.toString());
return;
}
//單層遍歷結(jié)果
int digit = digits.charAt(index) - '0'; // 將index指向的數(shù)字轉(zhuǎn)為int
String letters = letterMap[digit];
for(int i = 0; i < letters.length(); i++){
s.append(letters.chatAt(i)); //把letters中對(duì)應(yīng)的字母放進(jìn)來
backtracking(digits, index + 1);
s.deleteCharAt(s.length() - 1);
//如果把回溯隱藏在參數(shù)中就是：
//void getCombinations(const string& digits, int index, const string& s)
//getCombinations(digits, index + 1, s + letters[i]);
}
}
public List<String> letterCombinations(String digits) {
result.clear();
s.setLength(0); // 清空StringBuilder
if (digits.length() == 0) {
return result;
}
backtracking(digits, 0);
return result;
}
class Solution {
private String[] letterMap = {
"", // 0
"", // 1
"abc", // 2
"def", // 3
"ghi", // 4
"jkl", // 5
"mno", // 6
"pqrs",// 7
"tuv", // 8
"wxyz" // 9
};
private List<String> result = new ArrayList<>();
private StringBuilder s = new StringBuilder();
private void backtracking(String digits, int index){
if(index == digits.length()){
result.add(s.toString());
return;
}
int digit = digits.charAt(index) - '0';
String letters = letterMap[digit];
for(int i = 0; i < letters.length(); i++){
s.append(letters.charAt(i));
backtracking(digits, index+1);
s.deleteCharAt(s.length() - 1);
}
}
public List<String> letterCombinations(String digits) {
result.clear();
s.setLength(0);
if (digits.length() == 0) {
return result;
}
backtracking(digits, 0);
return result;
}
}
