學習參考
回溯
與遞回相輔相成;回溯是遞回的副產品，只要有遞回就會有回溯，
回溯函式也就是遞回函式，指的都是一個函式，
回溯搜索法
純暴力搜索
解決的問題
組合問題：N個數里面按一定規則找出k個數的集合
切割問題：一個字串按一定規則有幾種切割方式
子集問題：一個N個數的集合里有多少符合條件的子集
排列問題：N個數按一定規則全排列，有幾種排列方式(與組合差別，排列有元素順序)
棋盤問題：N皇后，解數獨等等
理解
抽象的不易理解；抽象為圖形結構--樹形結構
N叉樹【樹的寬度：集合的大小（for處理）；深度：遞回的深度（遞回處理）】
模板
void backtracking(引數){
if(終止條件){
收集結果；
return；
}
//單層搜索
for(選擇：本層集合中元素（樹中節點孩子的數量就是集合的大小)）{//集合元素集
處理節點；
backtracking(路徑，選擇串列);//遞回函式；
回溯操作； //（12，把2回溯，變13；沒有回溯操作就會遞回為123）
}
return；
}
遞回里面嵌套for回圈，for回圈里又有遞回
leetcode題目
組合
77.組合
for回圈嵌套太多層了
樹形結構
不能取前面的的：因為組合是無序的，會重復；
每個節點都是一個for回圈
回溯三部曲
遞回函式引數回傳值
確定終止條件
單層遞回邏輯
偽代碼
全域變數：二維陣列res【回傳值】
一維陣列path【單個結果】
//確定回傳值引數
void backtracking(n,k,start){//n集合大小；k需要的子集合大小；start每個取值的開始；
//確定終止條件
if(path.size == k){
res.add(path);
return;
}
//單層遞回邏輯
//對于1，234節點
for(i=start,i<=n;i++){
path.push(i);//1
backtracking(n,k,i+1);//遍歷剩下的集合234；
path.pop();//回溯程序
}
}
實作
java版本
class Solution {
List<List<Integer>> res = new ArrayList<List<Integer>>();
List<Integer> path = new ArrayList<Integer>();
public List<List<Integer>> combine(int n, int k) {
backtracking(n,k,1);
return res;
}
public void backtracking(int n,int k,int start){
if(path.size() == k){
res.add(new ArrayList<>(path));//容易犯錯誤
return;
}
for(int i=start;i<=n;i++){//i<=n -(k-path.size()) + 1 會減少運行時間【剪枝操作】
path.add(i);
backtracking(n,k,i+1);
path.remove(path.size()-1);
}
}
}
問題：參考
在鏈表path里面添加值，然后把path鏈表添加進res鏈表中，在做演算法題的時候，平時使用res.add(path)，結果發現輸出列印為空：
| 在鏈表path里面添加值，然后把path鏈表添加進res鏈表中，在做演算法題的時候，平時使用res.add(path)，結果發現輸出列印為空： | res.add(new ArrayList＜＞(path))和res.add(path)的區別 |
|---|---|
| 共同點： | 都是向res這個ArrayList中填加了一個名為path的鏈表 |
| 不同點： | res.add(new ArrayList(path))：開辟一個獨立地址，地址中存放的內容為path鏈表，后續path的變化不會影響到res |
| res.add(path)：將res尾部指向了path地址，后續path內容的變化會導致res的變化， |
優化：剪枝
可以剪枝的地方就在遞回中每一層的for回圈所選擇的起始位置，
如果for回圈選擇的起始位置之后的元素個數 已經不足 我們需要的元素個數了，那么就沒有必要搜索了，
優化程序如下：
已經選擇的元素個數：path.size();
所需需要的元素個數為: k - path.size();
串列中剩余元素（n-i） >= 所需需要的元素個數（k - path.size()）
在集合n中至多要從該起始位置 : i <= n - (k - path.size()) + 1，開始遍歷
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/549996.html
標籤：其他
上一篇：服務器通用背板管理(UBM)實作