2021/04/01
回溯法（原地 swap）
这个是网上流传的最简洁的版本，但是不是很好理解，这里用到了 swap 方法，直接在原数组中整理数据。
区间 [0, idx) 表示已经排列好了的部分，每一次需要选择 idx 可以放置的元素，直到 idx == len 的时候表示某个排列结束了。
对于 [idx, len) 的任何元素，都可以通过 swap 方法放置到 idx 的位置。
impl Solution {
pub fn permute(mut nums: Vec<i32>) -> Vec<Vec<i32>> {
let mut result = vec![];
Solution::permute0(&mut nums, 0, &mut result);
return result
}
fn permute0<T:PartialEq + Clone>(arr: &mut Vec<T>, idx: usize, result: &mut Vec<Vec<T>>) {
let len = arr.len();
if idx == len {
result.push(arr.clone());
return;
}
for i in idx..len {
arr.swap(i, idx);
Solution::permute0(arr, idx + 1, result);
arr.swap(i, idx);
}
}
}
回溯法（使用 collector）
这个方法是我做了带重复元素的全排列后重新回来写这道题使用的。
代码中 idx 表示的是 collector 数组的当前长度，当 collector 数组排列满了之后，就得到了一个排列。
这里需要引入一个 vis 数组来记录 arr 中哪些元素已经参与排列了，每一次从 arr 中选择出所有还没有参与排列的元素 push 进 collector 参与排列，同时标记这个元素被使用过了。
impl Solution {
pub fn permute(mut nums: Vec<i32>) -> Vec<Vec<i32>> {
let mut vis: Vec<bool> = (0..nums.len()).map(|x| false).collect();
let mut result = vec![];
Solution::permutation_collector(&mut nums, 0, &mut vis, &mut vec![], &mut result);
return result;
}
pub fn permutation_collector<T: PartialEq + Copy>(arr: &mut Vec<T>, idx: usize, vis: &mut Vec<bool>, collector: &mut Vec<T>, res: &mut Vec<Vec<T>>) {
if collector.len() == arr.len() {
res.push(collector.clone());
return;
}
for i in 0..arr.len() { // arr 中所有还没有参与排列的元素都可以 push 进 collector
if vis[i] {
continue;
}
collector.push(arr[i]);
vis[i] = true;
Solution::permutation_collector(arr, idx + 1, vis, collector, res);
collector.pop();
vis[i] = false;
}
}
}