Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
Each number in C may only be used once in the combination.
Note:
A solution set is:
1, 7
1, 2, 5
2, 6
1, 1, 6
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
if (candidates == null || candidates.length == 0) {
return new ArrayList<List<Integer>>();
}
Set<List<Integer>> rt = new HashSet<List<Integer>>();
ArrayList<Integer> cur = new ArrayList<Integer>();
Arrays.sort(candidates);
dfs(0, target, rt, cur, candidates);
return new ArrayList<List<Integer>>(rt);
}
private void dfs(int start, int target, Set<List<Integer>> rt,
ArrayList<Integer> cur, int[] candidates) {
if (target == 0) {
rt.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 + 1, target - candidates[i], rt, cur, candidates);
cur.remove(cur.size() - 1);
}
}
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。