Combination Sum II LeetCode solution in Java

1
class Solution {
2
  public List<List<Integer>> combinationSum2(int[] candidates, int target) {
3
    List<List<Integer>> res = new ArrayList<>();
4
    List<Integer> path = new ArrayList<>();
5
    // O(nlogn)
6
    Arrays.sort(candidates);
7
    boolean[] visited = new boolean[candidates.length];
8
    helper(res, path, candidates, visited, target, 0);
9
    return res;
10
  }
11

12
  private void helper(
13
      List<List<Integer>> res,
14
      List<Integer> path,
15
      int[] candidates,
16
      boolean[] visited,
17
      int remain,
18
      int currIndex) {
19
    if (remain == 0) {
20
      res.add(new ArrayList<>(path));
21
      return;
22
    }
23
    if (remain < 0) {
24
      return;
25
    }
26

27
    for (int i = currIndex; i < candidates.length; i++) {
28
      if (visited[i]) {
29
        continue;
30
      }
31
      if (i > 0 && candidates[i] == candidates[i - 1] && !visited[i - 1]) {
32
        continue;
33
      }
34
      int curr = candidates[i];
35
      path.add(curr);
36
      visited[i] = true;
37
      helper(res, path, candidates, visited, remain - curr, i + 1);
38
      path.remove(path.size() - 1);
39

40
      visited[i] = false;
41
    }
42
  }
43
}