/
githubmirror
/
hello-algo
Обзор
Документация
Войти
/
githubmirror
/
hello-algo
Код
Запросы
0
Пакеты
0
Релизы
0
Аналитика
Безопасность
main
codes/rust/chapter_backtracking/permutations_i.rs
46 строк
1 KB
rongyi
Make rust more idomatic (#1386)
13 июн 2024, 10:19
Не верифицирован
13 июн 2024, 10:19
017b95f
Код
Авторство
О чём код?
/* * File: permutations_i.rs * Created Time: 2023-07-15 * Author: codingonion (coderonion@gmail.com) */ /* 回溯算法：全排列 I */ fn backtrack(mut state: Vec<i32>, choices: &[i32], selected: &mut [bool], res: &mut Vec<Vec<i32>>) { // 当状态长度等于元素数量时，记录解 if state.len() == choices.len() { res.push(state); return; } // 遍历所有选择 for i in 0..choices.len() { let choice = choices[i]; // 剪枝：不允许重复选择元素 if !selected[i] { // 尝试：做出选择，更新状态 selected[i] = true; state.push(choice); // 进行下一轮选择 backtrack(state.clone(), choices, selected, res); // 回退：撤销选择，恢复到之前的状态 selected[i] = false; state.pop(); } } } /* 全排列 I */ fn permutations_i(nums: &mut [i32]) -> Vec<Vec<i32>> { let mut res = Vec::new(); // 状态（子集） backtrack(Vec::new(), nums, &mut vec![false; nums.len()], &mut res); res } /* Driver Code */ pub fn main() { let mut nums = [1, 2, 3]; let res = permutations_i(&mut nums); println!("输入数组 nums = {:?}", &nums); println!("所有排列 res = {:?}", &res); }