leetcode/Problem40/Solution.java at master · gorthitk/leetcode · GitHub

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
29
30
31
32
33
34
35
36
37
38


import java.util.*;

public class Solution
{
    public List<List<Integer>> combinationSum2(int[] candidates, int target)
    {
        Arrays.sort(candidates);
        List<List<Integer>> result = new ArrayList<>();
        getCombinations(candidates, 0, target, new ArrayList<Integer>(), result);
        return result;
    }

    private void getCombinations(int[] candidates, int curr, int target, ArrayList<Integer> path,
                                 List<List<Integer>> result)
    {
        if (target == 0)
        {
            result.add(new ArrayList<>(path));
            return;
        }
        if (target < 0)
        {
            return;
        }
        for (int i = curr; i < candidates.length; i++)
        {
            if (i > curr && candidates[i] == candidates[i - 1])
            {
                continue;
            }
            path.add(candidates[i]);
            getCombinations(candidates, i + 1, target - candidates[i], path, result);
            path.remove(path.size() - 1);
        }
    }
}