为什么 buf.pop() 重复调用一次 dfs 就通过了？ 实在是不明白，这里先感谢大佬热心解答
给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
https://leetcode-cn.com/problems/subsets-ii/
下面这个是我的试出来的代码，本来只是随手复制了一行代码结果运行通过了。
use std::collections::HashSet;
impl Solution {
pub fn subsets_with_dup(nums: Vec<i32>) -> Vec<Vec<i32>> {
start(&nums)
}
}
fn start(nums: &[i32]) -> Vec<Vec<i32>> {
let mut ans = HashSet::new();
dfs(0, nums.len() as i32, nums, &mut vec![], &mut ans);
ans.into_iter().collect()
}
fn dfs(next: usize, depth: i32, nums: &[i32], buf: &mut Vec<i32>, set: &mut HashSet<Vec<i32>>) {
if depth < 0 || next >= nums.len() {
let mut buf = buf.clone();
buf.sort_unstable();
set.insert(buf);
return;
}
buf.push(nums[next]);
println!("buf: {:?},next == {}", buf, next);
dfs(next + 1, depth - 1, nums, buf, set);
buf.pop();
dfs(next + 1, depth - 1, nums, buf, set);
}
Ext Link: https://leetcode-cn.com/problems/subsets-ii/solution/ma-fan-da-shen-gen-wo-shuo-yi-xia-zhe-ge-0v6o/
1
共 2 条评论, 1 页
评论区
写评论第一步
枚举包含 nums[next] 的所有子集。
pop 之后是枚举不包含 nums[next] 的所有子集。
为求简洁，假设原来的集合里没有重复元素（有重复的情况是类似的，这里只是为了解释起来简单），并且设集合为{x_1, x_2, ..., x_n}. 那么将这个集合的幂集分为两种，含有x_1的和不含有x_1的，可以发现这两种集合是一一对应的，每一个不含有x_1的集合加上x_1一定对应一个含有x_1的集合，反之亦然。另外一个性质就是，不含有x_1的那些集合恰好组成了{x_2, ..., x_n}的幂集。令M(i)表示{x_i,...,x_n}的幂集，那么我们发现M(i) = M(i+1) + ({x_i} ^ M(i+1)). 其中这里的+是集合并，^表示把x_i加入到M(i+1)中每一个集合。这个dfs就差不多这个意思，
buf.push把x_i加入到当前构造的集合中，dfs求M(i+1)，buf.pop把x_i去掉，dfs再来一次。