77. Combinations Medium

1/**
2 * [77] Combinations
3 *
4 * Given two integers n and k, return all possible combinations of k numbers out of the range [1, n].
5 * You may return the answer in any order.
6 *  
7 * Example 1:
8 * 
9 * Input: n = 4, k = 2
10 * Output:
11 * [
12 *   [2,4],
13 *   [3,4],
14 *   [2,3],
15 *   [1,2],
16 *   [1,3],
17 *   [1,4],
18 * ]
19 * 
20 * Example 2:
21 * 
22 * Input: n = 1, k = 1
23 * Output: [[1]]
24 * 
25 *  
26 * Constraints:
27 * 
28 * 1 <= n <= 20
29 * 1 <= k <= n
30 * 
31 */
32pub struct Solution {}
33
34// problem: https://leetcode.com/problems/combinations/
35// discuss: https://leetcode.com/problems/combinations/discuss/?currentPage=1&orderBy=most_votes&query=
36
37// submission codes start here
38
39impl Solution {
40    pub fn combine(n: i32, k: i32) -> Vec<Vec<i32>> {
41        let mut result: Vec<Vec<i32>> = Vec::new();
42        Self::dfs(&mut result, &mut vec![], 1, n, k);
43        result
44    }
45
46    fn dfs(result: &mut Vec<Vec<i32>>, current: &mut Vec<i32>, index: i32, n: i32, k: i32) {
47        if current.len() == k as usize {
48            result.push(current.clone());
49        }
50
51        for i in index..n + 1 {
52            current.push(i);
53            Self::dfs(result, current, i + 1, n, k);
54            current.pop();
55        }
56    }
57}
58
59// submission codes end
60
61#[cfg(test)]
62mod tests {
63    use super::*;
64
65    #[test]
66    fn test_77() {
67        Solution::combine(4, 2);
68    }
69}
70