回溯
子集
- 个人观点，回溯就是用深度优先搜素哦的形式去穷举出所有可能性,例如子集。
- 我们可以用树状的形式把可能性人工列出来 如下图
//直接套用二叉树的逻辑
impl Solution {
pub fn subsets(nums: Vec<i32>) -> Vec<Vec<i32>> {
let mut ans=vec![];
let mut path=vec![];
fn dfs(ans:&mut Vec<Vec<i32>>,path:&mut Vec<i32>,i:usize,n:usize,nums:&Vec<i32>){
if i==n{
ans.push(path.clone());
return;
}else{
path.push(nums[i]);
dfs(ans, path, i+1, n, nums);
}
}
dfs(&mut ans, &mut path, 0, nums.len(), &nums);
ans
}
}- 我们发现结果不对，答案是输入套了一层数组的壳就没了。
- 这时候我们就需要引入回溯的思想了。
- 已知我们的答案是
ans是全局共享，那我们就可以通过对ans进行操作来记录下每次循环ans的结果。 - 这就需要我们保存上一次的状态来开启下一次的函数，则跳跃了本次。
//直接套用二叉树的逻辑
impl Solution {
pub fn subsets(nums: Vec<i32>) -> Vec<Vec<i32>> {
let mut ans=vec![];
let mut path=vec![];
fn dfs(ans:&mut Vec<Vec<i32>>,path:&mut Vec<i32>,i:usize,n:usize,nums:&Vec<i32>){
if i==n{
ans.push(path.clone());
return;
}else{
path.push(nums[i]);
dfs(ans, path, i+1, n, nums);
path.pop();
dfs(ans, path, i+1, n, nums);
}
}
dfs(&mut ans, &mut path, 0, nums.len(), &nums);
ans
}
}
进阶问题
使用set去个重就好了
// 处理重复元素，需要先排序
impl Solution {
pub fn subsets_with_dup(mut nums: Vec<i32>) -> Vec<Vec<i32>> {
nums.sort_unstable(); // 排序以便处理重复元素
let mut ans = vec![];
let mut path = vec![];
fn dfs(ans: &mut Vec<Vec<i32>>, path: &mut Vec<i32>, i: usize, nums: &Vec<i32>) {
ans.push(path.clone());
for j in i..nums.len() {
// 剪枝：跳过重复元素
if j > i && nums[j] == nums[j-1] {
continue;
}
path.push(nums[j]);
dfs(ans, path, j + 1, nums);
path.pop();
}
}
dfs(&mut ans, &mut path, 0, &nums);
ans
}
}