Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
The same repeated number may be chosen from C unlimited number of times.
Note:
- All numbers (including target) will be positive integers.
- Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
- The solution set must not contain duplicate combinations.
For example, given candidate set 2,3,6,7 and target 7,
A solution set is: [7] [2, 2, 3]
Subscribe to see which companies asked this question
【题目解析】
给定一个候选数字序列一个目标值，找到所有的和等于目标值的候选数字组合。同一个候选数字可以出现多次。
1. 所有的数字是正数；
2. 组合中的数字降序排列；
3. 结果中不能存在相同的组合；
【思路】
首先我们从一个简单的例子分析一下这样组合生成的过程：
[1,2,3] target = 7
我们从[1,2,3]生成所有的和等于7的数字组合，可以分为以1开头的有：
[1,1,1,1,1,1,1],[1,1,1,1,1,2],[1,1,1,1,3],[1,1,1,2,2],[1,1,2,3],[1,2,2,2],[1,3,3]
以2开头的：
[2,2,3]
上面这几个组合是满足所有条件的组合。生成过程可以这样描述：
1. 给定一个升序排序的数组；
2. 从数组头部向后遍历，如果遇到一个比目标值小的数n，我们找到目标值为target - n的所有组合，如果找到这样的组合，那么我们把n合并到每一个组合里；
3. 如果遇到一个值m = target 则新建一个List，添加m后返回；
4. 如果遇到一个值m > target 则终结遍历，因为之后的数字肯定比target还大；
很明显这是一个递归的过程，在这个过程中我们首先对候选数组进行了排序，这是为什么呢？ 因为在递归的过程中，如果一个数字n小于target，那么在递归求解target - n时我们可以确定一个从候选数组重新开始的下标，这个下标就是当前数字的下标。
【java代码】
public class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
Arrays.sort(candidates); //升序排序
return combination(candidates, target, 0);
}
public List<List<Integer>> combination(int[] candidates, int target, int start) {
List<List<Integer>> list = new ArrayList<>();
if(candidates == null || candidates.length == 0) return list;
for(int i = start; i < candidates.length; i++){
if(candidates[i] < target){
List<List<Integer>> tlist = combination(candidates, target - candidates[i], i);
if(tlist.size() > 0){
for(List<Integer> alist : tlist){
alist.add(0, candidates[i]);
}
list.addAll(tlist);
}
}
else if(candidates[i] == target){
List<Integer> tlist = new LinkedList<>();
tlist.add(target);
list.add(tlist);
}
else break;
}
return list;
}
}