題意理解：

????????一個?無重復元素?的整數數組?candidates?和一個目標整數?target?? ?

? ? ? ? 從candidates?取數字，使其和==?target?，有多少種組合（candidates?中的?同一個?數字可以?無限制重復被選取）

? ? ? ? 這道題和之前一道組合的區別：這道題允許重復的數字

解題思路：

? ? ? ? 組合問題——>遞歸

? ? ? ? 這道題特殊的地方，對組合內數字的和做了要求，而不是個數，一開始并不確定樹的深度，組合的大小是不定的。

1.暴力回溯+剪枝優化

class Solution {List<List<Integer>> result=new ArrayList<>();LinkedList<Integer> path=new LinkedList<>();int sum=0;public List<List<Integer>> combinationSum(int[] candidates, int target) {backtracking(candidates,target,0);return result;}public void backtracking(int[] candidates,int target,int index){//結果收集if(sum==target){result.add(new ArrayList<>(path));return;} else if (sum>target) {//剪枝return;}//遍歷分支for(int i=index;i<candidates.length;i++){path.add(candidates[i]);sum+=candidates[i];//遞歸backtracking(candidates,target,i);//回溯path.removeLast();sum-=candidates[i];}}
}

2.分析

時間復雜度：O()

? ? ? ? n個位置，每個位置有兩種可能選或不選。

? ? ? ? 時間復雜度和樹的深度有關，是所有可行解之和

空間復雜度：O(n)