Problem Statement

Find all valid combinations of k numbers that sum up to n such that the following conditions are true:

• Only numbers 1 through 9 are used.
• Each number is used at most once.

Return a list of all possible valid combinations. The list must not contain the same combination twice, and the combinations may be returned in any order.

LeetCode:

• https://leetcode.com/problems/combination-sum-iii/description/

Constraints

2 <= k <= 9
1 <= n <= 60

Examples

Example 1:

Input: k = 3, n = 7
Output: [
         [1, 2, 4]
        ]
        
Explanation:
1 + 2 + 4
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.

Different Approaches

Code:

With For Loop:

class Solution {
public:
    void solve(vector<vector<int>>& result, vector<int>& output, int target, int k, int start) {
        // Base Case: If we have exactly `k` numbers and `target` is met
        if (target == 0 && k == 0) {
            result.push_back(output); // Add current combination to result
            return;
        }

        // Terminate recursion if we've used `k` numbers or target is negative
        if (k == 0 || target < 0) {
            return;
        }

        // Loop from `start` to `9` to add unique elements to the combination
        for (int i = start; i <= 9; ++i) {
            output.push_back(i); // Include current number
            solve(result, output, target - i, k - 1, i + 1); // Move to the next number
            output.pop_back(); // Backtrack to explore other combinations
        }
    }

    vector<vector<int>> combinationSum3(int k, int n) {
        vector<vector<int>> result;  // To store all valid combinations
        vector<int> output;          // Temporary vector to build each combination

        solve(result, output, n, k, 1); // Start recursion with the first number
        return result;
    }
};

Without For Loop:

class Solution {
public:
    void solve(vector<vector<int>>& result, vector<int>& output, int target, int k, int start) {
        // Base Case: Found a valid combination
        if (target == 0 && k == 0) {
            result.push_back(output);
            return;
        }

        // If we run out of numbers or exceed the target, stop
        if (k == 0 || target < 0 || start > 9) {
            return;
        }

        // Include current number
        output.push_back(start);
        solve(result, output, target - start, k - 1, start + 1);
        output.pop_back(); // Backtrack

        // Exclude current number and move to the next number
        solve(result, output, target, k, start + 1);
    }

    vector<vector<int>> combinationSum3(int k, int n) {
        vector<vector<int>> result;  // To store all valid combinations
        vector<int> output;          // Temporary vector to build each combination

        solve(result, output, n, k, 1); // Start recursion with the first number
        return result;
    }
};