leetcode/Problem216/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


import java.util.ArrayList;
import java.util.List;

public class Solution
{
    public List<List<Integer>> combinationSum3(int k, int n)
    {
        List<List<Integer>> result = new ArrayList<>();
        getCombinations(n, 0, new ArrayList<>(), result, 1, k);
        return result;
    }

    private void getCombinations(int target, int currSum, List<Integer> curr, List<List<Integer>> result, int idx,
                                 int k)
    {
        if (currSum > target || curr.size() > k)
        {
            return;
        }
        if (currSum == target && curr.size() == k)
        {
            result.add(new ArrayList<>(curr));
            return;
        }
        for (int i = idx; i < 10; i++)
        {
            curr.add(i);
            getCombinations(target, currSum + i, curr, result, i + 1, k);
            curr.remove(curr.size() - 1);
        }
    }
}