给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明：
所有数字（包括 target）都是正整数。
解集不能包含重复的组合。
示例 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]
]
求解思路
方法一
回溯（递归）+剪枝来完成，剪枝是为了去重（比如示例1中的[2,2,3]和[2,3,2]）
方法二
动态规划求解
这里采用了方法一
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) {
//如果这次选的数比前面已经选了的数还要小，那么直接跳过
//这样等于剪枝工作，去掉可能重复的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中所有数的和等于target
//res小于0，则代表这条递归路径行不通
if (res == 0) {
mList.add(list1);
} else if (res > 0) {
find(list1, res);
}
}
}
}
