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:
For example, given candidate set 2,3,6,7 and target 7,
A solution set is:
7
2, 2, 3
使用递归,注意保存结果时,应该新建一个ArrayList:result.add(new ArrayList< Integer>(cur))。否则result会指向一直变化的cur。
public List<List<Integer>> combinationSum(int[] candidates, int target) {
if (candidates == null || candidates.length == 0) {
return new ArrayList<List<Integer>>();
}
List<List<Integer>> result = new ArrayList<List<Integer>>();
ArrayList<Integer> cur = new ArrayList<Integer>();
Arrays.sort(candidates);
dfs(0, target, result, cur, candidates);
return result;
}
private void dfs(int start, int target, List<List<Integer>> result,
ArrayList<Integer> cur, int[] candidates) {
if (target == 0) {
result.add(new ArrayList<Integer>(cur));
return;
}
for (int i = start; i < candidates.length; i++) {
// candidates[i] > target,则递归结束,后面不可能是解
if (candidates[i] > target) {
return;
}
cur.add(candidates[i]);
dfs(i, target - candidates[i], result, cur, candidates);
cur.remove(cur.size() - 1);
}
}
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。