leetcode--Combination Sum

 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 }