Combination Sum III

Intuition

To build the intuition to this problem imagine being a coach who needs to form a team of exactly k players from a pool of players numbered 1 through 9. Each player has a unique skill level represented by their number. The objective is to select players such that the sum of their skill levels equals a specific target, n. Each possible combination of players is considered to find all valid teams where the total skill level precisely matches the target.

In the recursion process, each player is considered in sequence to decide whether to include them in the current team. If included, the player's skill level is subtracted from the remaining target, and the process continues with the next player. If the player's skill level cannot be included, the process backtracks to explore alternative players. This continues until all possible team combinations are evaluated.

Approach

Initialize an empty list to store the valid combinations and another list to track the current combination being formed.
Define a recursive function that accepts the remaining target sum, the next number to consider, and the current combination.
Within the recursive function, check if the remaining sum is zero and the current combination size matches k. If true, add the combination to the result list.
If the remaining sum is less than zero or the combination size exceeds k, terminate the current path. Otherwise, iterate through the possible numbers, adding each to the current combination, calling the function recursively with updated parameters, and then removing the number to explore other paths.

<!--- <h3> Dry Run

---!>

Solution

#include <bits/stdc++.h>
using namespace std;

class Solution {
private: 
    // Recursive function to find combinations
    void func(int sum, int last, vector<int> &nums, int k, vector<vector<int>> &ans) {
        // If the sum is zero and the number of elements is k
        if(sum == 0 && nums.size() == k) {
            // Add the current combination to the answer
            ans.push_back(nums);
            return; 
        }
        // If the sum is less than or equal to zero or the number of elements exceeds k
        if(sum <= 0 || nums.size() > k) return; 

        // Iterate from the last number to 9
        for(int i = last; i <= 9; i++) {
            // If the current number is less than or equal to the sum
            if(i <= sum) {
                // Add the number to the current combination
                nums.push_back(i); 
                // Recursive call with updated sum and next number
                func(sum - i, i + 1, nums, k, ans); 
                // Remove the last number to backtrack
                nums.pop_back(); 
            } else {
                // If the number is greater than the sum, break the loop
                break;
            }
        }
    } 
public:
    // Function to find all possible combinations of k numbers that add up to n
    vector<vector<int>> combinationSum3(int k, int n) {
        vector<vector<int>> ans; 
        vector<int> nums; 
        // Call the recursive function with initial parameters
        func(n, 1, nums, k, ans);
        return ans; 
    }
};

int main() {
    Solution sol;
    int k = 3; // Number of elements in the combination
    int n = 7; // Target sum
    vector<vector<int>> result = sol.combinationSum3(k, n);

    // Print the result
    for (const auto& combination : result) {
        for (int num : combination) {
            cout << num << " ";
        }
        cout << endl;
    }

    return 0;
}
import java.util.ArrayList;
import java.util.List;

class Solution {
    private void func(int sum, int last, List<Integer> nums, int k, List<List<Integer>> ans) {
        // If the sum is zero and the number of elements is k
        if (sum == 0 && nums.size() == k) {
            // Add the current combination to the answer
            ans.add(new ArrayList<>(nums));
            return;
        }
        // If the sum is less than or equal to zero or the number of elements exceeds k
        if (sum <= 0 || nums.size() > k) return;

        // Iterate from the last number to 9
        for (int i = last; i <= 9; i++) {
            // If the current number is less than or equal to the sum
            if (i <= sum) {
                // Add the number to the current combination
                nums.add(i);
                // Recursive call with updated sum and next number
                func(sum - i, i + 1, nums, k, ans);
                // Remove the last number to backtrack
                nums.remove(nums.size() - 1);
            } else {
                // If the number is greater than the sum, break the loop
                break;
            }
        }
    }

    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> nums = new ArrayList<>();
        // Call the recursive function with initial parameters
        func(n, 1, nums, k, ans);
        return ans;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int k = 3; // Number of elements in the combination
        int n = 7; // Target sum
        List<List<Integer>> result = sol.combinationSum3(k, n);

        // Print the result
        for (List<Integer> combination : result) {
            for (int num : combination) {
                System.out.print(num + " ");
            }
            System.out.println();
        }
    }
}
class Solution:
    def func(self, sum, last, nums, k, ans):
        # If the sum is zero and the number of elements is k
        if sum == 0 and len(nums) == k:
            # Add the current combination to the answer
            ans.append(list(nums))
            return
        # If the sum is less than or equal to zero or the number of elements exceeds k
        if sum <= 0 or len(nums) > k:
            return

        # Iterate from the last number to 9
        for i in range(last, 10):
            # If the current number is less than or equal to the sum
            if i <= sum:
                # Add the number to the current combination
                nums.append(i)
                # Recursive call with updated sum and next number
                self.func(sum - i, i + 1, nums, k, ans)
                # Remove the last number to backtrack
                nums.pop()
            else:
                # If the number is greater than the sum, break the loop
                break

    def combinationSum3(self, k, n):
        ans = []
        nums = []
        # Call the recursive function with initial parameters
        self.func(n, 1, nums, k, ans)
        return ans

# Example usage
sol = Solution()
k = 3  # Number of elements in the combination
n = 7  # Target sum
result = sol.combinationSum3(k, n)

# Print the result
for combination in result:
    print(combination)
class Solution {
    func(sum, last, nums, k, ans) {
        // If the sum is zero and the number of elements is k
        if (sum === 0 && nums.length === k) {
            // Add the current combination to the answer
            ans.push([...nums]);
            return;
        }
        // If the sum is less than or equal to zero or the number of elements exceeds k
        if (sum <= 0 || nums.length > k) return;

        // Iterate from the last number to 9
        for (let i = last; i <= 9; i++) {
            // If the current number is less than or equal to the sum
            if (i <= sum) {
                // Add the number to the current combination
                nums.push(i);
                // Recursive call with updated sum and next number
                this.func(sum - i, i + 1, nums, k, ans);
                // Remove the last number to backtrack
                nums.pop();
            } else {
                // If the number is greater than the sum, break the loop
                break;
            }
        }
    }

    combinationSum3(k, n) {
        let ans = [];
        let nums = [];
        // Call the recursive function with initial parameters
        this.func(n, 1, nums, k, ans);
        return ans;
    }
}

// Example usage
let sol = new Solution();
let k = 3; // Number of elements in the combination
let n = 7; // Target sum
let result = sol.combinationSum3(k, n);

// Print the result
result.forEach(combination => {
    console.log(combination.join(' '));
});

Complexity Analysis

Time Complexity The time complexity is O(2^9 * k), due to the exploration of all subsets of the set {1, 2, ..., 9}.

Space Complexity The space complexity is O(k), due to the maximum depth of the recursion stack, which is k.

Problem List

Examples:

Constraints

Hints

Company Tags

Editorial

Intuition

Approach

Solution

Complexity Analysis

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code