Combination Sum

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 (a₁, a₂, … , a_k) must be in non-descending order. (ie, a₁ â‰¤ a₂ â‰¤ … ≤ a_k).
• 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] 

Hing: use recursion. Iterate through the sorted candidate array. Start from the first element of the array. Use a temp buffer to store the number you have picked. Each element can be picked multiple times. There are three situation. If the sum equals the target, then output this temp buffer. If the sum is less than target, continue the selection process from the next position. If it's already greater than the target, abort this temp buffer. An important thing is that, you never go back again to smaller values. As the above example, you start from [2], then [2, 2], and [2,2,2]. When you select [2, 2, 2, 2], you find it is already larger than 7, so just abort it. Then 2, 2, 3, which is an result. Then you find 2, 2, 6...and you just abort this selection, then starting [2, 3]..., [3], [3,3]....

01 public ArrayList<ArrayList<Integer>> combinationSum(int[] candidates, int target) {
02     ArrayList<ArrayList<Integer>> results=new ArrayList<ArrayList<Integer>>();
03     if(candidates.length==0)
04         return results;
05     ArrayList<Integer> temp=new ArrayList<Integer>();
06     Arrays.sort(candidates);
07     doCombine(results, temp, candidates, 0, target);
08     return results;
09   
10 }
11 
12 public void doCombine(ArrayList<ArrayList<Integer>> results, ArrayList<Integer> temp, int [] candidates, int start, int target)
13 {
14   //Iterate through each number. Start from the first number.
15   //Each number can be used multiple times, until we pick up the next number
16     for(int i=start;i<candidates.length;i++)
17     {
18       //Base case: target equals the current number, add it to the temp buffer, output it.
19         if(target-candidates[i]==0)
20         {
21             temp.add(candidates[i]);
22             ArrayList<Integer> out=new ArrayList<Integer>(temp);
23             results.add(out);
24           
25         }
26       //Target larger than the current number, then new target becomes target-candidates[i].
27       //Add candidates[i] to the temp buffer. Call the fuction itself recursively
28         else if(target-candidates[i]>0)
29         {
30               
31             temp.add(candidates[i]);
32             doCombine(results, temp, candidates, i, target-candidates[i]);
33         }
34 
35       //Target smaller than the current number. Such combination is not valid. Return.
36         else
37         {
38             return;
39         }
40        //Remove the last element of the temporary buffer
41         int size=temp.size();
42         if(size>0)
43             temp.remove(size-1);
44     }
45 }