216. Combination Sum III

Published on April 17, 2023

Question

Given a target number n and a limitation k, where k is the quantity of number requirement for the combination. Find the combination of 1-9 to the sum n.

Algorithm

This is much similar to the other combination questions. The limitation is n and quantity is k.

Code

class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> res = new ArrayList<>();
        if (k < 2 || k > 9 || n < 1 || n > 60) {
            return res;
        }
        helper(res, k, n, 0, 1, new ArrayList<>());
        return res;
    }
    
    private void helper(List<List<Integer>> res, int k, int n, int sum, int index, List<Integer> list) {
        if (sum == n) {
            if (list.size() == k) {
                res.add(new ArrayList<>(list));
            }
        } else if (sum < n) {
            for (int i = index; i <= 9; i++) {
                list.add(i);
                helper(res, k, n, sum+i, i+1, list);
                list.remove(list.size() - 1);
            }
        }
    }
}