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.