## 216. Combination Sum III

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.

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. [1,2,1] is not valid because 1 is used twice.
```

Example 4:

```Input: k = 3, n = 2
Output: []
Explanation: There are no valid combinations.
```

Example 5:

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

Constraints:

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

## Rust Solution

``````struct Solution;

impl Solution {
fn combination_sum3(k: i32, n: i32) -> Vec<Vec<i32>> {
if k > 9 {
return vec![];
}
let nums: Vec<i32> = (1..10).collect();
let mut cur = vec![];
let mut res = vec![];
Self::dfs(0, n, &mut cur, &mut res, &nums, k as usize);
res
}
fn dfs(
start: usize,
target: i32,
cur: &mut Vec<i32>,
all: &mut Vec<Vec<i32>>,
nums: &[i32],
n: usize,
) {
if cur.len() == n {
if target == 0 {
all.push(cur.to_vec());
}
} else {
if target > 0 && start < nums.len() {
Self::dfs(start + 1, target, cur, all, nums, n);
cur.push(nums[start]);
Self::dfs(start + 1, target - nums[start], cur, all, nums, n);
cur.pop();
}
}
}
}

#[test]
fn test() {
let k = 3;
let n = 7;
let res = vec_vec_i32![[1, 2, 4]];
assert_eq!(Solution::combination_sum3(k, n), res);
let k = 3;
let n = 9;
let mut res = vec_vec_i32![[1, 2, 6], [1, 3, 5], [2, 3, 4]];
let mut ans = Solution::combination_sum3(k, n);
res.sort_unstable();
ans.sort_unstable();
assert_eq!(ans, res);
}
``````

Having problems with this solution? Click here to submit an issue on github.