Enumerate Fixed-Size Distinct Digit Combinations
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
Return all combinations of exactly k different numbers chosen from 1 through 9 whose sum is n. Use each number at most once. Do not return a combination twice. Combinations and their collection may be presented without imposing an additional order; rearranging members does not create a new combination.
```cpp
vector<vector<int>> combinationSum3(int k, int n);
```
### Examples
```text
Input: k = 2, n = 10
One valid output: [[1,9],[2,8],[3,7],[4,6]]
```
```text
Input: k = 3, n = 6
Output: [[1,2,3]]
```
### Constraints & Assumptions
- `2 <= k <= 9`.
- `1 <= n <= 60`.
- All selected numbers must be distinct integers from 1 through 9.
### What a Strong Answer Covers
- Exactly k selections with the requested sum and no repeated number.
- Complete combination coverage without permutation duplicates.
- Impossible totals and output-sensitive copying cost.
### Follow-up Questions
- Why is `[5,5]` invalid for k=2 and n=10?
- What happens when the requested sum exceeds 1+2+...+9?
Overview: Enumerate all distinct 1-through-9 member combinations of an exact size and sum without imposing result order.
