Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.
Each number in candidates 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.Example 1:
Input: candidates = [10,1,2,7,6,1,5], target = 8, A solution set is: [ [1, 7], [1, 2, 5], [2, 6], [1, 1, 6] ]Example 2:
Input: candidates = [2,5,2,1,2], target = 5, A solution set is: [ [1,2,2], [5] ]
题意：
给定一个集合以及一个值target，找出所有加起来等于target的组合。（每个元素只能用一次）
Solution1： Backtracking
在[leetcode]39. Combination Sum组合之和的基础上， 加一行查重的动作。
code
1 class Solution { 2 public List<List<Integer>> combinationSum2(int[] candidates, int target) { 3 Arrays.sort(candidates); 4 List<List<Integer>> result = new ArrayList<>(); 5 List<Integer> path = new ArrayList<>(); 6 helper(candidates, 0, target, path, result ); 7 return result; 8 } 9 10 private void helper(int[] nums, int index, int remain, List<Integer> path, List<List<Integer>> result){ 11 if (remain == 0){ 12 result.add(new ArrayList<>(path)); 13 return; 14 } 15 for(int i = index; i < nums.length; i++){ 16 if (remain < nums[i]) return; 17 if(i > index && nums[i] == nums[i-1]) continue; /** skip duplicates */ 18 path.add(nums[i]); 19 helper(nums, i + 1, remain - nums[i], path, result); 20 path.remove(path.size() - 1); 21 } 22 } 23 }
转载于:https://www.cnblogs.com/liuliu5151/p/10707581.html
