77. Combinations
Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.
You may return the answer in any order.
Example 1:
Input: n = 4, k = 2 Output: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]
Example 2:
Input: n = 1, k = 1 Output: [[1]]
Constraints:
1 <= n <= 20
1 <= k <= n
Rust Solution
struct Solution;
impl Solution {
fn combine(n: i32, k: i32) -> Vec<Vec<i32>> {
let mut res = vec![];
let nums: Vec<i32> = (1..=n).collect();
let n = n as usize;
let k = k as usize;
let mut cur: Vec<i32> = vec![];
Self::dfs(0, 0, &mut cur, &mut res, &nums, n, k);
res
}
fn dfs(
start: usize,
count: usize,
cur: &mut Vec<i32>,
all: &mut Vec<Vec<i32>>,
nums: &[i32],
n: usize,
k: usize,
) {
if count == k {
all.push(cur.to_vec());
} else {
for i in start..n {
cur.push(nums[i]);
Self::dfs(i + 1, count + 1, cur, all, nums, n, k);
cur.pop();
}
}
}
}
#[test]
fn test() {
let n = 4;
let k = 2;
let mut res = vec_vec_i32![[2, 4], [3, 4], [2, 3], [1, 2], [1, 3], [1, 4]];
let mut ans = Solution::combine(n, k);
res.sort();
ans.sort();
assert_eq!(ans, res);
}
Having problems with this solution? Click here to submit an issue on github.