題目：

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

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

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

思路：

全局變量result存儲結(jié)果集，path存儲某一組合

第一步：確定參數(shù)與返回值。參數(shù)為candidates數(shù)組，target，sum（path數(shù)組中現(xiàn)有值之和），startIndex（遍歷的candidates數(shù)組下標(biāo)起始），無返回值

第二步：確定終止條件。當(dāng)target=sum時，獲取到一個組合，將組合加入到結(jié)果集中

第三步：確定單層遞歸邏輯。for循環(huán)遍歷candidates數(shù)組，從startIndex到candidates數(shù)組的最后一個元素。進行剪枝優(yōu)化操作，當(dāng)sum+candidates[i]>target時，就不必進行下去了。for循環(huán)里的步驟就是：更新sum，更新path，遞歸調(diào)用，回溯。

代碼：

    List<List<Integer>> result=new ArrayList<>();//結(jié)果集List<Integer> path=new ArrayList<>();//存儲某一組合public List<List<Integer>> combinationSum(int[] candidates, int target) {Arrays.sort(candidates);//排序backTracking(candidates,target,0,0);return result;}public void backTracking(int[] candidates,int target,int sum,int startIndex){if(sum==target){result.add(new ArrayList<>(path));return;}for(int i=startIndex;i<candidates.length&&sum+candidates[i]<=target;i++){sum+=candidates[i];path.add(candidates[i]);//處理backTracking(candidates,target,sum,i);//遞歸，注意從i開始，因為數(shù)字可重復(fù)sum-=candidates[i];//回溯path.remove(path.size()-1);}}