Find all valid combinations of k numbers that sum up to n such that the following conditions are true:
1 through 9 are used.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 <= 91 <= n <= 60struct 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);
}