pofk_algorithm 0.0.3

A collection of efficient algorithms implemented in Rust for real-world projects.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

//! Combinations (Generic, Production-Grade)
//!
//! Generates all possible combinations of k elements from a set.
//!
//! # Type Parameters
//! * `T`: Value type. Must implement `Clone`.
//!
//! # Example
//! ```rust
//! use pofk_algorithm::backtracking_algorithms::combinations::*;
//! let nums = vec![1, 2, 3, 4];
//! let combs = combinations(&nums, 2);
//! assert_eq!(combs.len(), 6);
//! ```
pub fn combinations<T: Clone>(nums: &[T], k: usize) -> Vec<Vec<T>> {
    let mut res = Vec::new();
    let mut comb = Vec::new();
    fn backtrack<T: Clone>(start: usize, nums: &[T], k: usize, comb: &mut Vec<T>, res: &mut Vec<Vec<T>>) {
        if comb.len() == k {
            res.push(comb.clone());
            return;
        }
        for i in start..nums.len() {
            comb.push(nums[i].clone());
            backtrack(i + 1, nums, k, comb, res);
            comb.pop();
        }
    }
    backtrack(0, nums, k, &mut comb, &mut res);
    res
}