組合總和

給你一個 無重復元素 的整數數組 candidates 和一個目標整數 target ，找出 candidates 中可以使數字和為目標數 target 的 所有 不同組合 ，并以列表形式返回。你可以按 任意順序 返回這些組合。
candidates 中的 同一個 數字可以 無限制重復被選取 。如果至少一個數字的被選數量不同，則兩種組合是不同的。

class Solution {  
    List<List<Integer>> result = new ArrayList<>();  
    List<Integer> path = new ArrayList<>();  
    public List<List<Integer>> combinationSum(int[] candidates, int target) {  
        Arrays.sort(candidates);//剪枝
        backingtracking(candidates,target,0,0);  
        return result;  
    }  
    public void backingtracking(int[] candidates, int target,int startIndex,int sum){  
        if(sum>target){  
            return;  
        }  
        if(sum == target){  
            //result.add(path);這里是錯誤的!  
            result.add(new ArrayList<>(path));  
            return;  
        }   
        for(int i = startIndex;i<candidates.length;i++){  
            if(sum+candidates[i]>target) break;//剪枝
            sum+=candidates[i];  
            path.add(candidates[i]);  
            backingtracking(candidates,target,i,sum);//這里不能傳入i+1,因為可以重復使用!  
            sum-=candidates[i];  
            path.remove(path.size()-1);  
        }  
    }  
}

具體區(qū)別

• res.add(path);
  這行代碼是將 path 這個列表的引用直接添加到 res 中。也就是說，res 中存儲的是指向同一個 path 對象的引用。
  因此，后續(xù)如果對 path 進行修改（比如添加或刪除元素），res 中對應的列表也會同步變化，因為它們指向的是同一個對象地址
• res.add(new ArrayList<>(path));
  這行代碼是創(chuàng)建了一個新的 ArrayList，并用 path 的當前元素初始化它，然后將這個新列表添加到 res 中。
  這樣，res 中存儲的是一個新的、獨立的列表對象，與原來的 path 不共享地址。
  后續(xù)對 path 的修改不會影響到已經添加到 res 中的列表內容

為什么通常用 res.add(new ArrayList<>(path));

在回溯算法或者類似場景中，path 通常是一個動態(tài)變化的列表，隨著遞歸的深入和回退不斷添加和刪除元素。如果直接用 res.add(path);，那么 res 中存儲的所有列表都會指向同一個 path，最終所有結果都會變成相同的（即最后一次修改后的狀態(tài)）。使用 new ArrayList<>(path) 可以保存當時的快照，保證結果的正確性

為什么剪枝操作先對數組進行排序
例如[2,3,5],target = 4;此時,2+2=4,后面的肯定大于4,可以剪枝

組合總和2

修改上面代碼,超出時間限制,因為contains很慢!所以要在for循環(huán)中做剪枝操作,去重

class Solution {  
    List<List<Integer>> result = new ArrayList<>();  
    List<Integer> path = new ArrayList<>();  
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {  
        Arrays.sort(candidates);//剪枝  
        boolean[] used = new boolean[candidates.length];  
        backingtracking(candidates,target,0,0,used);  
        return result;  
    }  
    public void backingtracking(int[] candidates, int target,int startIndex,int sum,boolean[] used){  
        if(sum>target){  
            return;  
        }  
        if(sum == target){  
            //result.add(path);這里是錯誤的!  
            /*if(!result.contains(path)){                result.add(new ArrayList<>(path));            }*/            result.add(new ArrayList<>(path));  
            return;  
        }  
        for(int i = startIndex;i<candidates.length;i++){  
            if(i>0&&candidates[i]==candidates[i-1]&&used[i-1]==false) continue;//相鄰元素相同,只判斷前一個元素,后面的會相同,實現了去重,這里的used數組只進行樹層去重,沒進行樹枝去重,符合題意  
            if(sum+candidates[i]>target) break;//剪枝  
            sum+=candidates[i];  
            path.add(candidates[i]);  
            used[i] = true;  
            backingtracking(candidates,target,i+1,sum,used);  
            sum-=candidates[i];  
            path.remove(path.size()-1);  
            used[i] = false;  
        }  
    }  
}

這里注意是樹枝去重還是數層去重!!!

分割回文串

不太懂

class Solution {  
    List<List<String>> result = new ArrayList<>();  
    List<String> path = new ArrayList<>();  
  
    public List<List<String>> partition(String s) {  
        backtracking(s, 0, new StringBuilder());  
        return result;  
    }  
  
    private void backtracking(String s, int start, StringBuilder sb) {  
        //因為是起始位置一個一個加的，所以結束時start一定等于s.length,因為進入backtracking時一定末尾也是回文，所以path是滿足條件的  
        if (start == s.length()) {  
            result.add(new ArrayList<>(path));  
            return;  
        }  
        //像前兩題一樣從前往后搜索，如果發(fā)現回文，進入backtracking,起始位置后移一位，循環(huán)結束照例移除path的末位  
        for (int i = start; i < s.length(); i++) {  
            sb.append(s.charAt(i));  
            //sb.toString().equals(sb.reverse().toString())不用這種方法,因為reverse會改變sb的內容  
            if (check(sb)) {  
                path.add(sb.toString());  
                backtracking(s, i + 1, new StringBuilder());  
                path.remove(path.size() - 1);  
            }  
        }  
    }  
    private boolean check(StringBuilder sb){  
        for (int i = 0; i < sb.length()/ 2; i++){  
            if (sb.charAt(i) != sb.charAt(sb.length() - 1 - i)){return false;}  
        }  
        return true;  
    }  
}