首页 > 代码库 > Leetcode-Combinations Sum II
Leetcode-Combinations Sum II
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.
- Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
- 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]
Have you met this question in a real interview?
Analysis:
Since there are duplicates, for each value, we get the number of elements that are this value. We sort the array, at each step in the recursion, we try to use 0 to elementNumOfCurValue number of this value. For next step, we directly skip to the next value.
Solution:
1 public class Solution { 2 public List<List<Integer>> combinationSum2(int[] num, int target) { 3 int[] candidates = num; 4 List<List<Integer>> resSet = new ArrayList<List<Integer>>(); 5 List<Integer> curRes = new ArrayList<Integer>(); 6 if (candidates.length==0) return resSet; 7 Arrays.sort(candidates); 8 int cur=0,end=candidates.length-1; 9 for (int i=0;i<candidates.length;i++)10 if (candidates[i]>target){11 end = i-1;12 break; 13 }14 15 16 sumRecur(candidates,cur,end,target,resSet,curRes);17 18 return resSet;19 20 }21 22 23 public void sumRecur(int[] candidates, int cur, int end, int valLeft, List<List<Integer>> resSet, List<Integer> curRes){24 if (valLeft==0){25 List<Integer> temp = new ArrayList<Integer>();26 temp.addAll(curRes);27 resSet.add(temp);28 return;29 }30 31 if (cur>end) return;32 33 int newLeft = valLeft;34 int curLen = curRes.size();35 int nextIndex = cur;36 while (nextIndex<=end && candidates[nextIndex]==candidates[cur]) nextIndex++;37 38 for (int i=cur;i<nextIndex;i++)39 if (newLeft>=candidates[i]){40 curRes.add(candidates[i]);41 newLeft -= candidates[i];42 sumRecur(candidates,nextIndex,end,newLeft,resSet,curRes);43 } else 44 break;45 46 while (curRes.size()!=curLen) curRes.remove(curRes.size()-1);47 48 sumRecur(candidates,nextIndex,end,valLeft,resSet,curRes); 49 }50 }
Leetcode-Combinations Sum II
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。