Combination Sum II
Description
Given an array num and a number target. Find all unique combinations in num where the numbers sum to target.
public class Solution {
/**
* @param num: Given the candidate numbers
* @param target: Given the target number
* @return: All the combinations that sum to target
*/
public List<List<Integer>> combinationSum2(int[] num, int target) {
// write your code here
List<List<Integer>> results = new ArrayList<>() ;
if(num == null || num.length == 0){
return results ;
}
Arrays.sort(num) ;
helper(num , target, 0 , results, new ArrayList<Integer>()) ;
return results ;
}
public void helper(int[] num, int remintarget , int start , List<List<Integer>> results, List<Integer> subset){
if(remintarget == 0){
results.add(new ArrayList<Integer>(subset)) ;
}
for(int i = start ; i < num.length ; i++ ){
if(remintarget < num[i]){
break ;
}
if(i != start && num[i] == num[i-1]){
continue ;
}
subset.add(num[i]);
helper(num , remintarget - num[i] , i+1 , results , subset) ;
subset.remove(subset.size()-1);
}
}
}