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:
- 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 2,3,6,7 and
target 7,
A solution set
is: [7] [2, 2, 3]
1 public class Solution { 2 public ArrayList<ArrayList<Integer>> combinationSum(int[] candidates, int target) { 3 ArrayList<ArrayList<Integer> > result = new ArrayList<ArrayList<Integer> >(); 4 ArrayList<ArrayList<Integer> > temp = new ArrayList<ArrayList<Integer> >(); 5 ArrayList<IndexSum> sum = new ArrayList<IndexSum>(); 6 Arrays.sort(candidates); 7 if(candidates.length > 0){ 8 for(int i = 0; i < candidates.length; ++i){ 9 if(candidates[i] <= target){ 10 ArrayList<Integer> nodes = new ArrayList<Integer>(); 11 nodes.add(candidates[i]); 12 temp.add(nodes); 13 sum.add(new IndexSum(i, candidates[i])); 14 } 15 else 16 break;; 17 } 18 while(!temp.isEmpty()){ 19 ArrayList<Integer> aNode = temp.remove(0); 20 IndexSum aPair = sum.remove(0); 21 if(aPair.sum == target) 22 result.add(aNode); 23 if(aPair.sum < target){ 24 for(int i = aPair.index; i < candidates.length; ++i){ 25 if(aPair.sum + candidates[i] < target){ 26 ArrayList<Integer> newNode = new ArrayList<Integer>(); 27 newNode.addAll(aNode); 28 newNode.add(candidates[i]); 29 temp.add(newNode); 30 IndexSum newPair = new IndexSum(i, aPair.sum + candidates[i]); 31 sum.add(newPair); 32 } 33 else if(aPair.sum + candidates[i] == target){ 34 aNode.add(candidates[i]); 35 result.add(aNode); 36 } 37 else 38 break; 39 } 40 } 41 } 42 } 43 return result; 44 } 45 } 46 47 class IndexSum{ 48 int index; 49 int sum; 50 IndexSum(int i, int s){ index = i; sum = s;} 51 }