LeetCode 39. 組合總和 40.組合總和II 131.分割迴文串

歡迎關註個人公眾號：愛喝可可牛奶

LeetCode 39. 組合總和 40.組合總和II 131.分割迴文串

LeetCode 39. 組合總和

分析

回溯可看成對二叉樹節點進行組合枚舉，分為橫向和縱向

每次往sum添加新元素時，必須明確從can哪個位置開始，定義變數pos

返回條件 sum == target 或 sum > target; 橫向結束條件 沒有新元素可以添加了即pos<can.length;

bt(can, sum, tar, pos){
	if(sum == tar) add return;
    if(sum > tar) pos++ return;
    for(int i = pos; i < can.len;i++){
        sum+=can[pos];
        bt(can, sum, tar, i);
        sum-=can[pos];
    }
}

這個回溯考慮sum > tar時， pos++不應該寫在第3行，這樣導致回溯減掉的元素值與遞歸添加的不一樣。而應該放在第4行for()中，只有當縱向回溯結束時(也就是很多個sum+=can[i]導致return後)，橫向遍歷才會往右移動；回溯第n個can[i] 回溯第n-1個can[i];

剪枝

一次回溯只能抵消一層遞歸；每次return只是從已經添加進sum的眾多can[i]中減掉一個

舉個慄子：

sum+= n個can[i]，回溯一次還剩n-1個can[i];這時要i++了；但是剩下的sum和這個i++後的新can[i]加起來可能也會超過tar，這步操作可以剪枝，避免進入新can[i]的遞歸；

for (int i = pos; i < candidates.size() && sum + candidates[i] <= target; i++)

代碼

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        
        Arrays.sort(candidates); // 先進行排序
        backtracking(candidates, target, 0, 0);
        return res;
    }

    public void backtracking(int[] candidates, int target, int sum, int idx) {
        // 找到了數字和為 target 的組合
        if (sum == target) {
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i = idx; i < candidates.length; i++) {
            // 如果 sum + candidates[i] > target 就終止遍歷
            if (sum + candidates[i] > target) break;
            path.add(candidates[i]);
            backtracking(candidates, target, sum + candidates[i], i);
            path.removeLast(); // 回溯，移除路徑 path 最後一個元素
        }
    }
}

LeetCode 40.組合總和II

分析

在原有基礎上設限每個數字在每個組合中只能使用 一次 且不包含重覆的組合

Arrays升序；縱向遍歷時就要i++；Set去重

Set去重超時了！！！ 要在添加集合的時候就判斷是否重覆，取res中最後一個path和當前滿足條件的path比較 也不行

縱向遞歸不需要去重，橫向遞歸時採用去重

代碼

class Solution {
    List<List<Integer>> res = new LinkedList();
    LinkedList<Integer> path = new LinkedList();
    int sum = 0;
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates); // 先進行排序
        backtracking(candidates, target, 0);
        return res;
    }

    public void backtracking(int[] candidates, int target, int idx) {
        // 找到了數字和為 target 的組合
        if (sum == target) {
            res.add(new LinkedList<>(path));
            return;
        }

        for (int i = idx; i < candidates.length && sum + candidates[i] <= target; i++) {
            // 要對橫向遍歷時使用過的元素進行跳過 因為一樣的元素在深度遞歸時已經把包含此元素的所有可能結果全部枚舉過了
            if (i > idx && candidates[i] == candidates[i - 1]) {
                continue;
            }
            path.add(candidates[i]);
            sum += candidates[i];
            //System.out.println("sum="+sum);
            //i++;
            backtracking(candidates, target, i+1);
            //i--;
            //sum -= candidates[i];
            sum-=path.getLast();
            path.removeLast(); // 回溯，移除路徑 path 最後一個元素
        }
    }
}

LeetCode 131.分割迴文串

分析

切割子串，保證每個子串都是 迴文串

找到所有的子串組合，判斷子串是否是迴文串，根據索引切割 startIndex endIndex if(start-end) is ; res.add

代碼

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

    public List<List<String>> partition(String s) {
        backTracking(s, 0);
        return res;
    }

    private void backTracking(String s, int startIndex) {
        //如果起始位置大於s的大小，說明找到了一組分割方案
        if (startIndex >= s.length()) {
            res.add(new ArrayList(path));
            return;
        }
        for (int i = startIndex; i < s.length(); i++) {
            //如果是迴文子串，則記錄
            if (isPalindrome(s, startIndex, i)) {
                String str = s.substring(startIndex, i + 1);
                path.add(str);
            } else {
                continue;
            }
            //起始位置後移，保證不重覆
            backTracking(s, i + 1);
            // 一定要有回溯 開始下一種分割
            path.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;
    }
}

總結

1. 題目給定的數據集如果使用數組的方式，要判斷是否有序，沒有說明有序最好視情排序
2. 回溯橫向移動的時機一定是某個縱向遞歸結束
3. 看清題目要求，將串的所有子串都分割成迴文子串
4. 橫向遍歷邏輯 縱向遞歸startIndex++邏輯 回溯邏輯