dsalgo/
enumerate_combinations_inplace_iterative.rs

1pub fn combinations(
2    n: usize,
3    k: usize,
4) -> Vec<Vec<usize>> {
5    assert!(k <= n);
6
7    let mut res = vec![];
8
9    let mut a: Vec<_> = (0..k).collect();
10
11    loop {
12        res.push(a.clone());
13
14        let mut i = k;
15
16        for j in (0..k).rev() {
17            if a[j] != j + n - k {
18                i = j;
19
20                break;
21            }
22        }
23
24        if i == k {
25            return res;
26        }
27
28        a[i] += 1;
29
30        for j in i + 1..k {
31            a[j] = a[j - 1] + 1;
32        }
33    }
34}
35
36#[cfg(test)]
37
38mod tests {
39
40    use super::*;
41
42    #[test]
43
44    fn test() {
45        let res = combinations(5, 3);
46
47        assert_eq!(
48            res,
49            [
50                [0, 1, 2],
51                [0, 1, 3],
52                [0, 1, 4],
53                [0, 2, 3],
54                [0, 2, 4],
55                [0, 3, 4],
56                [1, 2, 3],
57                [1, 2, 4],
58                [1, 3, 4],
59                [2, 3, 4]
60            ]
61        );
62    }
63}