lintcode（153）数字组合 II

组合 II"/>

lintcode（153）数字组合 II

描述：

给出一组候选数字(C)和目标数字(T),找出C中所有的组合，使组合中数字的和为T。C中每个数字在每个组合中只能使用一次。

样例：

给出一个例子，候选数字集合为[10,1,6,7,2,1,5] 和目标数字 8  ,

解集为：[[1,7],[1,2,5],[2,6],[1,1,6]]

注意事项

• 所有的数字(包括目标数字)均为正整数。
  
• 元素组合(a1, a2, … , ak)必须是非降序(ie, a1 ≤ a2 ≤ … ≤ ak)。
  
• 解集不能包含重复的组合。 

首先要对num进行排序，以保证a1<=a2<=...<=ak，然后进行递归，注意每次将temp添加到result 中时要进行复制，temp 在递归的过程中会被修改，并且添加之前要查重。一个数字有两个选择，进入temp和不进temp，所以要调用两次递归，并且要对temp复原。

public class Solution {/*** @param num: Given the candidate numbers* @param target: Given the target number* @return: All the combinations that sum to target* 坑了好久  终于过了  注意把判断start放在三个判断的最后  而且temp要复制之后再添加到result*/public List<List<Integer>> combinationSum2(int[] num, int target) {// write your code hereList<List<Integer>> result = new ArrayList<List<Integer>>();if(num == null || num.length == 0)return result;Arrays.sort(num);ArrayList<Integer> temp = new ArrayList<Integer>();search(num , target , 0 , 0 ,result ,temp);return result;}public void search(int[] num , int target , int sum , int start , List<List<Integer>> result , ArrayList<Integer> temp){if(sum > target){return;}if(sum == target){ArrayList<Integer> nums = new ArrayList<Integer>(temp);if(!result.contains(nums)){result.add(nums);}return;}if(start >= num.length){return;}temp.add(num[start]);search(num , target , sum + num[start] , start + 1,result,temp);temp.remove(temp.size() - 1);search(num , target , sum , start + 1 , result , temp);}
}