給定一個(gè)無(wú)重復(fù)元素的數(shù)組 candidates 和一個(gè)目標(biāo)數(shù) target 顷扩，找出 candidates 中所有可以使數(shù)字和為 target 的組合。
candidates 中的數(shù)字可以無(wú)限制重復(fù)被選取丹弱。
說(shuō)明：
所有數(shù)字（包括 target）都是正整數(shù)。
解集不能包含重復(fù)的組合铲咨。
示例 1:
輸入: candidates = [2,3,6,7], target = 7,
所求解集為:
[
[7],
[2,2,3]
]
示例 2:
輸入: candidates = [2,3,5], target = 8,
所求解集為:
[
[2,2,2,2],
[2,3,3],
[3,5]
]
求解思路
方法一
回溯（遞歸）+剪枝來(lái)完成躲胳，剪枝是為了去重（比如示例1中的[2,2,3]和[2,3,2]）
方法二
動(dòng)態(tài)規(guī)劃求解
這里采用了方法一
public class CombinationSum {
int[] candidates;
int target;
List<List<Integer>> mList = new ArrayList<>();
public static void main(String[] args) {
int[] arr = {2, 3, 5};
int tar = 8;
CombinationSum combinationSum = new CombinationSum();
combinationSum.combinationSum(arr, tar);
}
public List<List<Integer>> combinationSum(int[] candidates, int target) {
this.candidates = candidates;
this.target = target;
find(new ArrayList<>(), target);
//System.out.println(mList);
return mList;
}
public void find(List<Integer> list, int num) {
if (num < 0) {
return;
}
//遍歷遞歸
for (int candidate : candidates) {
//如果這次選的數(shù)比前面已經(jīng)選了的數(shù)還要小，那么直接跳過(guò)
//這樣等于剪枝工作纤勒，去掉可能重復(fù)的list
if (!list.isEmpty() && candidate < list.get(list.size() - 1)) {
continue;
}
List<Integer> list1 = new ArrayList<>(list);
list1.add(candidate);
int res = num - candidate;
//res為0坯苹，代表list1中所有數(shù)的和等于target
//res小于0，則代表這條遞歸路徑行不通
if (res == 0) {
mList.add(list1);
} else if (res > 0) {
find(list1, res);
}
}
}
}
