题目
Given a set of candidate numbers (C) (without duplicates) 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.
The solution set must not contain duplicate combinations.
答案
class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> list = new ArrayList<List<Integer>>();
List<Integer> curr = new ArrayList<>();
Arrays.sort(candidates);
recur(candidates, target, 0, list, curr, 0);
return list;
}
private void recur(int[] candidates, int target, int curr_sum, List<List<Integer>> list, List<Integer> curr, int start) {
if(curr_sum == target) {
list.add(new ArrayList<>(curr));
return;
}
if(curr_sum > target) return;
for(int i = start; i < candidates.length; i++) {
curr.add(candidates[i]);
recur(candidates, target, curr_sum + candidates[i], list, curr, i);
curr.remove(curr.size() - 1);
}
}
}
