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`

77. Combinations
``````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);
}
``````