學習參考

回溯

與遞歸相輔相成;回溯是遞歸的副產品，只要有遞歸就會有回溯。
回溯函數(shù)也就是遞歸函數(shù)，指的都是一個函數(shù)。

回溯搜索法

純暴力搜索
解決的問題

組合問題：N個數(shù)里面按一定規(guī)則找出k個數(shù)的集合
切割問題：一個字符串按一定規(guī)則有幾種切割方式
子集問題：一個N個數(shù)的集合里有多少符合條件的子集
排列問題：N個數(shù)按一定規(guī)則全排列，有幾種排列方式(與組合差別，排列有元素順序)
棋盤問題：N皇后，解數(shù)獨等等

理解

抽象的不易理解；抽象為圖形結構--樹形結構
N叉樹【樹的寬度：集合的大?。╢or處理）；深度：遞歸的深度（遞歸處理）】

模板

void backtracking(參數(shù)){
  if(終止條件){
    收集結果；
    return；
  }

  //單層搜索
   for(選擇：本層集合中元素（樹中節(jié)點孩子的數(shù)量就是集合的大小)）{//集合元素集
      處理節(jié)點；
      backtracking(路徑，選擇列表);//遞歸函數(shù)；
      回溯操作； //（12，把2回溯，變13；沒有回溯操作就會遞歸為123）
    }
  return；
}

遞歸里面嵌套for循環(huán)，for循環(huán)里又有遞歸

leetcode題目

組合

77.組合

for循環(huán)嵌套太多層了

樹形結構

不能取前面的的：因為組合是無序的，會重復；
每個節(jié)點都是一個for循環(huán)

回溯三部曲

遞歸函數(shù)參數(shù)返回值
確定終止條件
單層遞歸邏輯

偽代碼

全局變量：二維數(shù)組res【返回值】
         一維數(shù)組path【單個結果】
//確定返回值參數(shù)
void backtracking(n,k,start){//n集合大小；k需要的子集合大?。籹tart每個取值的開始；
  //確定終止條件
  if(path.size == k){
    res.add(path);
    return;
  }
  //單層遞歸邏輯
  //對于1，234節(jié)點
  for(i=start,i<=n;i++){
    path.push(i);//1
    backtracking(n,k,i+1);//遍歷剩下的集合234；
    path.pop();//回溯過程
  } 
}

實現(xiàn)
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)，結果發(fā)現(xiàn)輸出打印為空：

優(yōu)化：剪枝
可以剪枝的地方就在遞歸中每一層的for循環(huán)所選擇的起始位置。

如果for循環(huán)選擇的起始位置之后的元素個數(shù) 已經不足 我們需要的元素個數(shù)了，那么就沒有必要搜索了。

優(yōu)化過程如下：

已經選擇的元素個數(shù)：path.size();
所需需要的元素個數(shù)為: k - path.size();
列表中剩余元素（n-i） >= 所需需要的元素個數(shù)（k - path.size()）
在集合n中至多要從該起始位置 : i <= n - (k - path.size()) + 1，開始遍歷

分割

131. 分割回文串

樹形結構

回溯三部曲

遞歸函數(shù)參數(shù)返回值
確定終止條件
單層遞歸邏輯

偽代碼
收集結果路徑

void backtracking(string s,startIndex){
    //終止條件
    //即切割線是終止條件
    if(startIndex >= s.length()){
        res.add(path);
        return;
    }

    //單層遞歸邏輯
    //切割字串范圍：(startIndex,i]
    for(i=startIndex;i< s.length();i++){
      if(isPalindrome(s,startIndex,i)){
          path.add(子串)；
      }else continue；
      
      backtracking(s,i+1);
      path.remove(path.size()-1);
    }
}

實現(xiàn)

java版本

class Solution {
    List<List<String>> result = new ArrayList<List<String>>();
    List<String> path = new ArrayList<String>();

    public List<List<String>> partition(String s) {
        backtracking(s,0);
        return result;
    }

    public void backtracking(String s,int startIndex){
        if(startIndex >= s.length()){
            result.add(new ArrayList<String>(path));
            return;
        }

        for(int i=startIndex;i<s.length();i++){
            String sub = s.substring(startIndex,i+1);
            if(isPalindrome(sub)){
                path.add(sub);
            }else {continue;}

            backtracking(s,i+1);
            path.remove(path.size()-1);
        }
    }

    public boolean isPalindrome(String s){
        int left = 0;
        int right = s.length()-1;

        while(left<right){
            if(s.charAt(left) != s.charAt(right)){
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}

子集問題

78. 子集

樹形結構

收獲結果的時候：在每個節(jié)點收獲結果
組合和分割問題都是在葉子節(jié)點里取結果；
偽代碼

void backtracking(nums,stratIndex){
  result.add(path);

  if(stratIndex >= path.size()) return;

  for(int i=startIndex;i<nums.length;i++){
    path.add(nums[i]);
    backtracking(nums,i+1);
    path.remove(path.size()-1);
  }
}

實現(xiàn)

class Solution {
    List<List<Integer>> list = new ArrayList<List<Integer>>();
    List<Integer> path= new ArrayList<Integer>();
    public List<List<Integer>> subsets(int[] nums) {
        backtracking(nums,0);
        return list;
    }

    public void backtracking(int[] nums,int stratIndex){
        list.add(new ArrayList<Integer>(path));
        if(stratIndex>=nums.length){
            return;
        }

        for(int i=stratIndex;i<nums.length;i++){
            path.add(nums[i]);
            backtracking(nums,i+1);
            path.remove(path.size()-1);
        }
    }
} 

排列

46.全排列

樹形結構

偽代碼：文章來源地址http://www.zghlxwxcb.cn/news/detail-412147.html

void backtracking(nums,used){
  if(path.size() == nums.length){
    res.add(path);
    return;
  }

  for(i=0;i<nums.length;i++){
    if(used[i] == true) continue;
    used[i] = true;
    path.add(nums[i]);
    backtracking(nums,used);
    used[i] = false;
    path.remove(path.size()-1);
  }
}

實現(xiàn)

class Solution {
    List<List<Integer>> list = new ArrayList<List<Integer>>();
    List<Integer> path = new ArrayList<Integer>();

    public List<List<Integer>> permute(int[] nums) {
        boolean[] used = new boolean[nums.length];
        backtracking(nums,used);
        return list;
    }

    public void backtracking(int[] nums,boolean[] used){
        if(path.size() >= nums.length){
            list.add(new ArrayList<>(path));
            return;
        }

        for(int i=0;i<nums.length;i++){
            if(used[i] == true) continue;
            
            path.add(nums[i]);
            used[i] = true;
            backtracking(nums,used);
            path.remove(path.size()-1);
            used[i] = false;
        }
    }
}

到了這里，關于回溯理論基礎及l(fā)eetcode例題的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！