Combination Sum LeetCode solution in Java

1
class Solution {
2
  public List<List<Integer>> combinationSum(int[] candidates, int target) {
3
    List<Integer> cur = new ArrayList<>();
4
    List<List<Integer>> result = new ArrayList<>();
5
    Arrays.sort(candidates);
6
    dfs(0, candidates, target, 0, cur, result);
7
    return result;
8
  }
9

10
  public void dfs(
11
      int start,
12
      int[] candidates,
13
      int target,
14
      int sum,
15
      List<Integer> cur,
16
      List<List<Integer>> result) {
17
    if (sum == target) {
18
      result.add(new ArrayList<>(cur));
19
      return;
20
    }
21
    for (int i = start; i < candidates.length; i++) {
22
      if (sum + candidates[i] <= target) {
23
        cur.add(candidates[i]);
24
        dfs(i, candidates, target, sum + candidates[i], cur, result);
25
        cur.remove((cur.size() - 1));
26
      }
27
    }
28
    return;
29
  }
30
}