Leetcode - Combination Sum

 1 public class Solution {
 2     public List<List<Integer>> combinationSum(int[] candidates, int target) {
 3         List<List<Integer>> res = new ArrayList<List<Integer>>();
 4         
 5         // sort candidates
 6         Arrays.sort(candidates);
 7         
 8         // call helpFunc to find all the combinations
 9         List<Integer> combo = new ArrayList<Integer>();
10         helpFunc(res, combo, candidates, 0, target);
11         
12         return res;
13     }
14     
15     public void helpFunc(List<List<Integer>> res, List<Integer> combo, int[] candidates, int idx, int remain) {
16         // end condition
17         if (remain == 0) {
18             res.add(new ArrayList<Integer>(combo));
19             return;
20         }
21         
22         // recursive
23         for (int i = idx; i < candidates.length; i++) {
24             if (candidates[i] <= remain) {
25                 combo.add(candidates[i]);
26                 helpFunc(res, combo, candidates, i, remain-candidates[i]);
27                 combo.remove(combo.size()-1);
28             }
29             else {
30                 return;
31             }
32         }
33     }
34 }