Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
The same repeated number may be chosen from C unlimited number of times.
Note:
For example, given candidate set 2,3,6,7 and target 7,
A solution set is: [7] [2, 2, 3]
思路
先对数组进行升序排列，然后在用回溯法BS，这里用的递归调用实现的
1 public class Solution { 2 public List<List<Integer>> combinationSum(int[] candidates, int target) { 3 Arrays.sort(candidates); 4 List<List<Integer>> result = new ArrayList<List<Integer>>(); 5 getResult(result, new ArrayList<Integer>(), candidates, target, 0); 6 7 return result; 8 } 9 10 private void getResult(List<List<Integer>> result, List<Integer> cur, int candidates[], int target, int start){ 11 if(target > 0){ 12 for(int i = start; i < candidates.length && target >= candidates[i]; i++){ 13 cur.add(candidates[i]); 14 getResult(result, cur, candidates, target - candidates[i], i); 15 cur.remove(cur.size() - 1); 16 }//for 17 }//if 18 else if(target == 0 ){ 19 result.add(new ArrayList<Integer>(cur)); 20 }//else if 21 } 22 }
原文：http://www.cnblogs.com/luckygxf/p/4239854.html