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:
All numbers (including target) will be positive integers.The solution set must not contain duplicate combinations.For example, given candidate set [10, 1, 2, 7, 6, 1, 5] and target 8,
A solution set is:
[ [1, 7], [1, 2, 5], [2, 6], [1, 1, 6]]Solution1:
public List<List<Integer>> combinationSum2(int[] candidates, int target) { Arrays.sort(candidates); return fullCombinationSum2(candidates, candidates.length - 1, target); } PRivate List<List<Integer>> fullCombinationSum2(int[] candidates, int len, int target) { List<List<Integer>> result = new ArrayList<>(); for (int i = len; i >= 0; i--) { if (candidates[i] < target) { List<List<Integer>> lists = fullCombinationSum2(candidates, i - 1, target - candidates[i]); if (!lists.isEmpty()) { for (List<Integer> list : lists) { list.add(candidates[i]); } result.removeAll(lists); result.addAll(lists); } } if (candidates[i] == target) { List<Integer> list = new ArrayList<>(); list.add(candidates[i]); result.remove(list); result.add(list); } } return result; }Solution2:
public List<List<Integer>> combinationSum2(int[] candidates, int target) { Arrays.sort(candidates); List<List<Integer>> result = new ArrayList<>(); fullCombinationSum2_1(candidates, 0, target, result, new ArrayList<>()); return result; } private void fullCombinationSum2(int[] candidates, int begin, int target, List<List<Integer>> result, List<Integer> temp) { if (target < 0) { return; } else if (target == 0 && result.indexOf(temp) < 0) { result.add(new ArrayList<>(temp)); } else { for (int i = begin; i < candidates.length; i++) { if (i > begin && candidates[i] == candidates[i-1]) continue; temp.add(candidates[i]); fullCombinationSum2_1(candidates, i + 1, target - candidates[i], result, temp); temp.remove(temp.size() - 1); } } }新闻热点
疑难解答
