给定一个候选数字的集合 candidates 和一个目标值 target. 找到 candidates 中所有的和为 target 的组合.
在同一个组合中, candidates 中的某个数字不限次数地出现.
所有数值 (包括 target ) 都是正整数.
返回的每一个组合内的数字必须是非降序的.
返回的所有组合之间可以是任意顺序.
解集不能包含重复的组合.
在线评测地址：LintCode 领扣
样例 1:
输入: candidates = [2, 3, 6, 7], target = 7
输出: [[7], [2, 2, 3]]
样例 2:
输入: candidates = [1], target = 3
输出: [[1, 1, 1]]
算法：DFS
解题思路
本题需要在给定一个候选数字的集合 candidates 中. 找到所有的和为目标值 target 的组合。
对于这种需要求解所有结果的问题，我们为了避免结果有遗漏或者重复，一般可以考虑使用搜索算法。而本题需要满足组合中选取的元素之和为一个目标值，这个可以作为深度优先搜索的边界判断条件，故本题可以使用深度优先搜索（DFS）算法。
算法流程
由于题目候选数字的集合candidates可能包含重复数字，且返回的结果要求组合内数字非降序，因此首先需对candidates进行升序排序并去重，得到新的数字集合candidatesNew；
对新的数字集合进行深度优先搜索，传入的参数包括：数字集合candidatesNew、当前的位置index、当前存入的组合current、距离目标值的差remainTarget、保存答案的列表result；
当remainTarget=0即达到边界，将current添加到result，回溯；
循环遍历index位置到数字集合的末尾，分别递归调用dfs；
递归步进为：remainTarget - candidatesNew[i]；
剪枝：当发现当前的数字加入已超过remainTarget可进行剪枝。
复杂度分析
时间复杂度：O(n^target/min), （拷贝过程视作O(1))，n为集合中数字个数，min为集合中最小的数字
每个位置可以取集合中的任意数字，最多有target/min个数字。
空间复杂度：O(n^target /min)，n为集合中数字个数，min为集合中最 小的数字
对于用来保存答案的列表，最多有n^target/min种组合
public class Solution {
/**
* @param candidates: A list of integers
* @param target:An integer
* @return: A list of lists of integers
*/
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> results = new ArrayList<>();
// 集合为空
if (candidates.length == 0) {
return results;
}
// 排序和去重
int[] candidatesNew = removeDuplicates(candidates);
// dfs
dfs(candidatesNew, 0, new ArrayList<Integer>(), target, results);
return results;
}
private int[] removeDuplicates(int[] candidates) {
//排序
Arrays.sort(candidates);
//去重
int index = 0;
for (int i = 0; i < candidates.length; i++) {
if (candidates[i] != candidates[index]) {
candidates[++index] = candidates[i];
}
}
int[] candidatesNew = new int[index + 1];
for (int i = 0; i < index + 1; i++) {
candidatesNew[i] = candidates[i];
}
return candidatesNew;
}
private void dfs(int[] candidatesNew, int index, List<Integer> current, int remainTarget, List<List<Integer>> results) {
// 到达边界
if (remainTarget == 0) {
results.add(new ArrayList<Integer>(current));
return;
}
// 递归的拆解：挑一个数放入current
for (int i = index; i < candidatesNew.length; i++) {
// 剪枝
if (remainTarget < candidatesNew[i]) {
break;
}
current.add(candidatesNew[i]);
dfs(candidatesNew, i, current, remainTarget - candidatesNew[i], results);
current.remove(current.size() - 1);
}
}
