039.Combination Sum

Posted on | In

Solution 1: accepted 18ms 80%

DFS. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public List<List<Integer>> combinationSum(int[] nums, int target) {
  List<List<Integer>> result = new ArrayList<List<Integer>>();
  List<Integer> list = new ArrayList<>();
  Arrays.sort(nums);
  comboHelper(result, list, nums, target, 0);
  return result;
}
public void comboHelper(List<List<Integer>> result, 
                      List<Integer> list, 
                      int[] nums, 
                      int remain,
                      int start) {
  if (remain == 0) {
      result.add(new ArrayList<Integer>(list));
  } else {
      // i = start will ignore the digits before so it won't repeat a sequence in different order
      for (int i = start; i < nums.length; i++) {  
          if (remain - nums[i] >= 0) { // exit condition
              list.add(nums[i]);
              comboHelper(result, list, nums, remain - nums[i], i);
              list.remove(list.size() - 1);
          } else { // since the array is sorted, no need to check the following numbers
              break;
          }
      }
  }
}