216. Combination Sum III – Leetcode Solutions

Example 1:

Input: k = 3, n = 7
Output: [[1,2,4]]
Explanation:
1 + 2 + 4 = 7
There are no other valid combinations.

Example 2:

Input: k = 3, n = 9
Output: [[1,2,6],[1,3,5],[2,3,4]]
Explanation:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
There are no other valid combinations.

Example 3:

Input: k = 4, n = 1
Output: []
Explanation: There are no valid combinations.
Using 4 different numbers in the range [1,9], the smallest sum we can get is 1+2+3+4 = 10 and since 10 > 1, there are no valid combination.

from typing import List

class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        # Helper function for backtracking
        def backtrack(start, current_combination, current_sum):
            # If the combination is of length k and the sum equals n, add it to the result
            if len(current_combination) == k and current_sum == n:
                results.append(list(current_combination))
                return
            
            # If the combination is too long or the sum exceeds n, stop exploring further
            if len(current_combination) > k or current_sum > n:
                return
            
            # Explore numbers from start to 9
            for i in range(start, 10):
                # Add the current number to the combination
                current_combination.append(i)
                # Recur with updated parameters: start from the next number, 
                # updated combination, and updated sum
                backtrack(i + 1, current_combination, current_sum + i)
                # Backtrack by removing the last added number
                current_combination.pop()
        
        # Initialize the result list
        results = []
        # Start the backtracking process from number 1
        backtrack(1, [], 0)
        return results

/**
 * @param {number} k
 * @param {number} n
 * @return {number[][]}
 */
var combinationSum3 = function(k, n) {
    // Helper function for backtracking
    const backtrack = (start, currentCombination, currentSum) => {
        // If the combination length equals k and the sum equals n, add to results
        if (currentCombination.length === k && currentSum === n) {
            results.push([...currentCombination]);
            return;
        }
        
        // If the combination length exceeds k or the sum exceeds n, stop further exploration
        if (currentCombination.length > k || currentSum > n) {
            return;
        }
        
        // Explore numbers from 'start' to 9
        for (let i = start; i <= 9; i++) {
            // Add the current number to the combination
            currentCombination.push(i);
            // Recur with updated parameters: next number, updated combination, updated sum
            backtrack(i + 1, currentCombination, currentSum + i);
            // Backtrack by removing the last added number
            currentCombination.pop();
        }
    };
    
    // Initialize the result array
    const results = [];
    // Start the backtracking process from number 1
    backtrack(1, [], 0);
    return results;
};

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

class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
        // This list will store all the valid combinations
        List<List<Integer>> results = new ArrayList<>();
        
        // Start the backtracking process
        backtrack(1, k, n, new ArrayList<>(), results);
        
        // Return the list of results
        return results;
    }
    
    // Helper method for backtracking
    private void backtrack(int start, int k, int n, List<Integer> currentCombination, List<List<Integer>> results) {
        // If we have used k numbers and the sum equals n, add this combination to the results
        if (currentCombination.size() == k && n == 0) {
            results.add(new ArrayList<>(currentCombination));
            return;
        }
        
        // If the combination is already too large or the sum is exceeded, stop the search
        if (currentCombination.size() > k || n < 0) {
            return;
        }
        
        // Explore the numbers from 'start' to 9
        for (int i = start; i <= 9; i++) {
            // Add the current number to the combination
            currentCombination.add(i);
            // Recursively call backtrack with updated parameters:
            // - Next starting number is i + 1 (because each number can only be used once)
            // - Reduce n by the current number (i)
            backtrack(i + 1, k, n - i, currentCombination, results);
            // Backtrack by removing the last added number to try another combination
            currentCombination.remove(currentCombination.size() - 1);
        }
    }
}

using System.Collections.Generic;

public class Solution {
    public IList<IList<int>> CombinationSum3(int k, int n) {
        // List to store the final results
        IList<IList<int>> results = new List<IList<int>>();
        
        // Start the backtracking process from number 1
        Backtrack(1, k, n, new List<int>(), results);
        
        // Return the list of all valid combinations
        return results;
    }
    
    // Helper method for backtracking
    private void Backtrack(int start, int k, int targetSum, List<int> currentCombination, IList<IList<int>> results) {
        // If the combination has exactly k numbers and their sum is equal to targetSum, add to results
        if (currentCombination.Count == k && targetSum == 0) {
            results.Add(new List<int>(currentCombination));
            return;
        }
        
        // If the combination size exceeds k or the sum goes below 0, stop exploring further
        if (currentCombination.Count > k || targetSum < 0) {
            return;
        }
        
        // Iterate over the numbers from 'start' to 9
        for (int i = start; i <= 9; i++) {
            // Add the current number to the combination
            currentCombination.Add(i);
            
            // Recur with the next number and updated target sum
            Backtrack(i + 1, k, targetSum - i, currentCombination, results);
            
            // Backtrack by removing the last added number to try another combination
            currentCombination.RemoveAt(currentCombination.Count - 1);
        }
    }
}