排列算法

permutation.rs

// 排列算法 P_{cnt}^{nums.len()}
fn permutation(nums: Vec<i32>, cnt: usize) -> Vec<Vec<i32>> {
    fn helper(result: &mut Vec<Vec<i32>>, nums: &mut Vec<i32>, cnt: usize, idx: usize) {
        if idx == cnt {
            result.push(Vec::from(&nums[..idx]));
            return;
        }

        // 第idx个元素可选择的方法
        for i in idx..nums.len() {
            nums.swap(idx, i);
            helper(result, nums, cnt, idx + 1);
            nums.swap(idx, i);
        }
    }

    if cnt == 0 {
        return vec![];
    }

    let mut nums = nums;
    let mut cnt = cnt;
    if cnt > nums.len() {
        cnt = nums.len();
    }

    let mut result = Vec::new();
    helper(&mut result, &mut nums, cnt, 0);
    result
}