216. Combination Sum III

Combination Sum III

Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.

Example 1: Input: k = 3, n = 7 Output:

[[1,2,4]]

Example 2: Input: k = 3, n = 9 Output:

[[1,2,6], [1,3,5], [2,3,4]]

Credits:Special thanks to @mithmatt for adding this problem and creating all test cases.

Solution

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

    private void help(int k, int n, int currentCount, int currentValue, List<Integer> current, List<List<Integer>> result, int index) {
        if (currentCount > k || currentValue > n) {
            return;
        }

        if (currentCount == k && currentValue == n) {
            result.add(new ArrayList<>(current));
            return;
        }

        if (currentCount == k) {
            return;
        }

        for (int i = index; i <= 9; i++) {
            if (current.contains(i)) {
                continue;
            }

            current.add(i);
            help(k, n, currentCount + 1, currentValue + i, current, result, i + 1);
            current.remove(current.size() - 1);
        }
    }
}