目錄

題目

思路

剪枝優(yōu)化

代碼

---

題目

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

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

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

示例?1：

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

示例?2：

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

示例 3：

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

思路

和前面的組合問(wèn)題不同的是，最后的結(jié)果集里的數(shù)字可以有重復(fù)比如target是4，結(jié)果集可以是2，2

本題沒(méi)有組合數(shù)量要求，僅僅是總和的限制，所以遞歸沒(méi)有層數(shù)的限制，只要選取的元素總和超過(guò)target，就返回！

本題還需要startIndex來(lái)控制for循環(huán)的起始位置?

對(duì)于組合問(wèn)題，什么時(shí)候需要startIndex呢？

如果是一個(gè)集合來(lái)求組合的話(huà)，就需要startIndex，例如：力扣77和216.

如果是多個(gè)集合取組合，各個(gè)集合之間相互不影響，那么就不用startIndex，例如：力扣17

注意以上只是說(shuō)求組合的情況，如果是排列問(wèn)題，又是另一套分析的套路.

終止只有兩種情況，sum大于target和sum等于target。

剪枝優(yōu)化

對(duì)總集合排序之后，如果下一層的sum（就是本層的 sum + candidates[i]）已經(jīng)大于target，就可以結(jié)束本輪for循環(huán)的遍歷。?

代碼

class Solution {public List<List<Integer>> combinationSum(int[] candidates, int target) {List<List<Integer>> result=new ArrayList<>();
//最后的結(jié)果集Arrays.sort(candidates);
//剪枝操作，先從小到大排序，如果哪個(gè)數(shù)已經(jīng)大于target了，那就不用再繼續(xù)往下了backTracking(result,new ArrayList<>(),candidates,target,0,0);return result;}public void backTracking(List<List<Integer>> result,List<Integer> path,int[] candidates,int target,int sum,int index){
//path保存葉子節(jié)點(diǎn)，target：目標(biāo)值，sum：葉子節(jié)點(diǎn)的和，index，遍歷的時(shí)候從哪個(gè)數(shù)開(kāi)始if(sum==target){//符合要求，把葉子節(jié)點(diǎn)加入結(jié)果集result.add(new ArrayList<>(path));return;}for(int i=index;i<candidates.length;i++){if(sum+candidates[i]>target) break;//大于了就不需要繼續(xù)往下了，剪枝path.add(candidates[i]);backTracking(result,path,candidates,target,sum+candidates[i],i);//最后一個(gè)數(shù)還是i因?yàn)樗詈蟮慕Y(jié)果集可以重復(fù)，比如2，3，4，選了2繼續(xù)往下的時(shí)候還可以選2path.remove(path.size() - 1); // 回溯，移除路徑 path 最后一個(gè)元素}}
}