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]
public List> combinationSum(int[] candidates, int target) {
List> ret=new ArrayList>();
if(candidates==null&&candidates.length==0){
return ret;
}
List path=new ArrayList<>();
Arrays.sort(candidates);
combinationSum(candidates, target,path,ret,0);
return ret;
}
public void combinationSum(int[] candidates, int target,
List path, List> ret, int index) {
// TODO 自动生成的方法存根
if (target == 0) {
// add the current set into the result.
ret.add(new ArrayList(path));
return;
}
if (target < 0) {
return;
}
int len=candidates.length;
for(int i=index;i
path.add(candidates[i]);
combinationSum(candidates, target-candidates[i], path, ret, i);
path.remove(path.size()-1);
}
}
阅读(348) | 评论(0) | 转发(0) |