組合總和

題目描述：

給你一個?無重復元素?的整數數組?candidates?和一個目標整數?target?，找出?candidates?中可以使數字和為目標數?target?的 所有?不同組合?，并以列表形式返回。你可以按?任意順序?返回這些組合。

candidates?中的?同一個?數字可以?無限制重復被選取?。如果至少一個數字的被選數量不同，則兩種組合是不同的。?

對于給定的輸入，保證和為?target?的不同組合數少于?150?個。

示例?1：

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

示例?2：

輸入: candidates = [2,3,5], target = 8
輸出: [[2,2,2,2],[2,3,3],[3,5]]

示例 3：

輸入: candidates = [2], target = 1
輸出: []

提示：

• 1 <= candidates.length <= 30
• 2 <= candidates[i] <= 40
• candidates?的所有元素?互不相同
• 1 <= target <= 40

思路分析：

? ? ? ? 使用深度優先遍歷?實現，使用一個列表，在?深度優先遍歷?變化的過程中，遍歷所有可能的列表并判斷當前列表是否符合題目的要求。如果不符合進行剪枝。

說明：

• 以 target = 7 為 根結點 ，創建一個分支的時 做減法 ；
• 每一個箭頭表示：從父親結點的數值減去邊上的數值，得到孩子結點的數值。邊的值就是題目中給出的 candidate 數組的每個元素的值；
• 減到 0或者負數的時候停止，即：結點 0和負數結點成為葉子結點；
• 同時每一次搜索的時候設置?下一輪搜索的起點?begin，即：從每一層的第?222?個結點開始，都不能再搜索產生同一層結點已經使用過的?candidate?里的元素。

代碼實現注解：

class Solution {public List<List<Integer>> combinationSum(int[] candidates, int target) {//定義一個返回結果的集合List<List<Integer>> res = new ArrayList<>();//定義一個存儲樹路徑上的節點值int len = candidates.length;if(len == 0)return res;//升序排序Arrays.sort(candidates);//定義一個表示數組的長度變量Deque<Integer> path = new ArrayDeque<>();//深度搜索，調用函數dfs(candidates, 0, len, target, path, res);return res;}private void dfs(int[] candidates, int begin, int len, int target, Deque<Integer> path,List<List<Integer>> res) {// 由于進入更深層的時候，小于 0 的部分被剪枝，因此遞歸終止條件值只判斷等于 0 的情況if (target == 0) {//將節點值存入返回集合res.add(new ArrayList<>(path));return;}//begin用于記錄當前遍歷位置for (int i = begin; i < len; i++) {//剪枝操作，將葉子節點小于0的分支減掉if (target - candidates[i] < 0) {break;}path.addLast(candidates[i]);//將i傳入可有效避免結果重復dfs(candidates, i, len, target - candidates[i], path, res);//回溯，移除path中最后一個元素path.removeLast();}}
}