Combination Sum III

Problem Statement

The task is to identify all unique combinations of k different numbers that sum up to n, adhering to specific conditions: the numbers used must be from the set {1, 2, 3, ..., 9}, and each number can be used at most once in any combination. The goal is to produce a list containing all such valid combinations. These combinations should not repeat within the list, and the sequence in which these combinations appear does not matter.

Examples

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.

Constraints

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

Approach and Intuition

Considering the constraints and requirements provided, the solution can be effectively approached using a backtracking algorithm. Here’s why and how:

1. Optimal Elements Choice:

   • We can only use the digits from 1 to 9.
   • This small range allows us to exhaustively search for all combinations without a large computational cost.

2. Backtracking Strategy:

   • Backtracking is suitable because it allows iterating over combinations of elements and "backtracking" as soon as a non-feasible path is identified.
   • Here, non-feasible paths could be when the sum of chosen numbers exceeds n or when more than k numbers are picked.

3. Implementation Details:

   • Begin with the smallest number (1) and move towards the highest (9).
   • At each step:
     • Include the current number into the running combination and proceed to the next number.
     • If the combination is valid (sum equals n and contains exactly k numbers), record it.
     • If the sum exceeds n or more than k numbers are included, backtrack by removing the last added number and try the next available number.
     • Continue this process until all combinations starting from the current number are checked, and then move to the next starting number.

4. Efficiency Considerations:

   • Remove numbers from consideration as soon as we know they will not lead to a valid solution (for example, if the current sum plus the smallest remaining number exceeds n).
   • Since the output combinations must be unique, and we systematically generate combinations, we do not need to worry about explicitly checking for duplicate combinations.

Examples Interpretation:

• For input (k = 3, n = 7): The only combination that sums up to 7 using exactly three numbers from 1 to 9 is [1, 2, 4].
• For input (k = 3, n = 9): There are several possible combinations like [1, 2, 6], [1, 3, 5], and [2, 3, 4].
• For input (k = 4, n = 1): It's impossible to achieve a sum of 1 using four numbers from the given range; hence, the result is an empty array.

Conclusion

Understanding the constraints of the problem and the properties of numbers involved allows us to efficiently design a backtracking solution to explore all potential combinations. This method ensures we only compute what's necessary, minimizing redundant calculations and checks.

Solutions

class Solution {
public:
    void explore(int left, int count, vector<int>& path, int start,
                 vector<vector<int>>& outputs) {
        if (left == 0 && path.size() == count) {
            outputs.push_back(path);
            return;
        } else if (left < 0 || path.size() == count) {
            return;
        }
    
        for (int j = start; j < 9; ++j) {
            path.push_back(j + 1);
            this->explore(left - j - 1, count, path, j + 1, outputs);
            path.pop_back();
        }
    }
    
    vector<vector<int>> combinationSum3(int count, int target) {
        vector<vector<int>> outputs;
        vector<int> path;
    
        this->explore(target, count, path, 0, outputs);
        return outputs;
    }
};