天氣漸寒，大家做好保暖措施。反正我在武漢是被凍傻了??。

首先，做任何有關(guān)回溯的題，一定要把這個遞歸函數(shù)模板記在心里！！

void backtracking(參數(shù)) {
    if (終止條件) {
        存放結(jié)果;
        return;
    }
    for (選擇本層集合中元素（畫成樹，就是樹節(jié)點孩子的大?。?{
        處理節(jié)點;
        backtracking();
        回溯，撤銷處理結(jié)果;
    }
}

組合總和問題

LeetCode 39：給你一個無重復(fù)元素的整數(shù)數(shù)組candidates和一個目標(biāo)整數(shù) target ，找出 candidates 中可以使數(shù)字和為目標(biāo)數(shù) target 的 所有不同組合 ，并以列表形式返回。你可以按任意順序返回這些組合。candidates 中的 同一個 數(shù)字可以 無限制重復(fù)被選取 。如果至少一個數(shù)字的被選數(shù)量不同，則兩種組合是不同的。數(shù)組中的元素滿足1 <= candidates[i] <= 200。

示例：

• 輸入：candidates = [2,3,6,7]，target = 7
• 輸出：[[2,2,3]，[7]]
• 解釋：2 和 3 可以形成一組候選，2 + 2 + 3 = 7 。注意2可以使用多次。7 也是一個候選， 7 = 7 ，僅有這兩種組合。

分析：首先，對于序列{2,3,6,7}，target=7?？梢韵冗x2，然后剩下的target就是7-2=5。再選一個2，剩余5-2=3。之后再選一個2，剩余3-2=1。已經(jīng)小于2了，我們不能繼續(xù)向下了，要撤回一下，看有沒有3。有3，就得到了第一個結(jié)果{2,2,3}。

然后，撤回到只選了一個2的時候，這時不能再取2了，而是從{3,6,7}中選擇，如下圖所示，沒有符合要求的！以此類推，后面嘗試從3、6和7開始選擇。

圖片

所以我們最終得到的結(jié)果就是{2,2,3}和{2,5}。

這個圖橫向是針對每個元素的暴力枚舉，縱向是遞歸，也是一個縱橫問題。

List<List<Integer>> res = new ArrayList<>(); //結(jié)果數(shù)組
List<Integer> path = new ArrayList<>(); //記錄當(dāng)前正在訪問的路徑
public List<List<Integer>> combinationSum(int[] candidates, int target) {
    dfs(candidates,0,target);
    return res;
}
public void dfs(int[] c,int u,int target){
    if(target < 0) return;
    if(target == 0){
        res.add(new ArrayList(path));
        return;
    }
    for(int i = u ; i < c.length;i++){
        if(c[i] <= target){
            path.add(c[i]);
            dfs(c,i,target-c[i]);
            path.remove(path.size() - 1);
        }
    }
}

配合上文提到的回溯模板你就會發(fā)現(xiàn)，這簡直就是標(biāo)準(zhǔn)的回溯題目。

分割字符串

LeetCode 131：給你一個字符串 s，請你將 s 分割成一些子串，使每個子串都是回文串。返回 s 所有可能的分割方案。

示例 1：

• 輸入：s = "aab"
• 輸出：[["a","a","b"],["aa","b"]]

示例 2：

• 輸入：s = "a"
• 輸出：[["a"]]

分析：每個子串都要是回文串，這個功能可以單獨寫一個函數(shù)用于判斷一個字符串是不是回文串。那么這個函數(shù)怎么實現(xiàn)呢？很簡單，利用雙指針分別指向字符串的首尾，一起往中間遍歷，一旦相同位置上的字符不相同就返回false，否則就默認(rèn)返回true。

還要再解決一個問題：如何分割？

圖片

上圖中，劃豎線分開的就是每次分出的子串，右邊就是還沒分的?？梢娒看畏殖鲆粋€的時候我們都要判斷一下是不是回文。

第一次切'a',第二次切'aa',第三次切'aab'。這對應(yīng)的就是回溯里的for循環(huán)，也就是橫向方面。第一次切了'a',剩下的就是'ab'。遞歸就是再將其再切一個回文下來，也就是第二個'a',剩下的'b'再交給遞歸進一步切割。這就是縱向方面要干的事情，其他以此類推。

用一個二維數(shù)組lists保存最后的結(jié)果。回想我們回溯的模板。首先想明白他的終止條件是什么？答：整個字符串都遍歷完之后。for循環(huán)就是圖中橫向的那一部分?；厮荩褪翘幚硗赀@種方案之后，退回的第一層，開始下一種分割方案。

List<List<String>> lists = new ArrayList<>();
Deque<String> deque = new LinkedList<>();

public List<List<String>> partition(String s) {
    backTracking(s, 0);
    return lists;
}
private void backTracking(String s, int startIndex) {
    //如果起始位置大于s的大小，說明找到了一組分割方案
    if(startIndex >= s.length()){
        lists.add(new ArrayList(deque));
        return;
    }
    for(int i = startIndex;i < s.length();i++){
        if(isPalindrome(s,startIndex,i)){
            String str = s.substring(startIndex,i+1);
            deque.addLast(str);
        }else{
            continue;
        }
        //起始位置后移，保證不重復(fù)
        backTracking(s,i+1);
        deque.removeLast();
    }
}
private boolean isPalindrome(String s,int startIndex,int end){
    for(int i = startIndex, j = end;i < j;i++ , j--){
        if(s.charAt(i) != s.charAt(j)){
            return false;
        }
    }
    return true;
}

看到這你依舊是蒙蒙？沒事，俺也一樣！（抱拳）這在力扣上都會被懷疑是不是困難題啊哈哈哈哈。

圖片

沒事沒事，我第一次的時候調(diào)代碼就調(diào)了半天，很正常，我一點事都沒有??。