LeetCode 216: Combination Sum III

Explanation

To solve this problem, we can use backtracking to generate all possible combinations of k numbers that sum up to n. We will start by defining a recursive function that takes the current combination, the current sum, the current number being considered, and the remaining numbers available. At each step, we will consider adding the current number to the combination and recursively call the function with updated values. We will keep track of the current sum and the number of elements in the combination to ensure we meet the conditions mentioned in the problem.

Algorithm

1. Initialize an empty list to store the valid combinations.
2. Define a recursive function that takes the current combination, current sum, current number being considered, remaining numbers available, and k.
3. In the recursive function:
   • If k is 0 and current sum is n, add the current combination to the list of valid combinations.
   • Otherwise, iterate over the remaining numbers and recursively call the function with updated parameters.
4. Call the recursive function with an empty combination, sum 0, start number 1, and remaining numbers 1 to 9.
5. Return the list of valid combinations.

Time Complexity

The time complexity of this algorithm is O(9 choose k), where k is the number of elements in a combination.

Space Complexity

The space complexity is O(k) for the recursion stack where k is the number of elements in a combination.

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

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

    private void backtrack(List<List<Integer>> result, List<Integer> tempList, int sum, int k, int n, int start) {
        if (k == 0 && sum == n) {
            result.add(new ArrayList<>(tempList));
            return;
        }
        for (int i = start; i <= 9; i++) {
            tempList.add(i);
            backtrack(result, tempList, sum + i, k - 1, n, i + 1);
            tempList.remove(tempList.size() - 1);
        }
    }
}