< 返回版块

so235 发表于 2021-03-31 05:32

为什么 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/

评论区

写评论
Grobycn 2021-03-31 10:11

第一步

buf.push(nums[next]);
dfs(next + 1, depth - 1, nums, buf, set);

枚举包含 nums[next] 的所有子集。

pop 之后是枚举不包含 nums[next] 的所有子集。

johnmave126 2021-03-31 08:47

为求简洁,假设原来的集合里没有重复元素(有重复的情况是类似的,这里只是为了解释起来简单),并且设集合为{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再来一次。

1 共 2 条评论, 1 页