企业官网建设流程全解析

LeetCode 78. 子集 Rust实现

数组元素互不相同，返回全部幂集子集。提供回溯DFS、迭代增量、位运算三种写法

1. 回溯 DFS（推荐，rust标准题解）

rust

impl Solution {
pub fn subsets(nums: Vec) -> Vec<Vec> {
let mut res = Vec::new();
let mut path = Vec::new();
Self::dfs(0, &nums, &mut path, &mut res);
res
}

fn dfs(start: usize, nums: &[i32], path: &mut Vec<i32>, res: &mut Vec<Vec<i32>>) { res.push(path.clone()); for i in start..nums.len() { path.push(nums[i]); Self::dfs(i + 1, nums, path, res); path.pop(); } }

}

2. 迭代增量法

逐个数字，复制已有子集并追加当前元素

rust

impl Solution {
pub fn subsets(nums: Vec) -> Vec<Vec> {
let mut res = vec![vec![]];
for &num in &nums {
let mut temp = Vec::new();
for item in &res {
let mut new_sub = item.clone();
new_sub.push(num);
temp.push(new_sub);
}
res.extend(temp);
}
res
}
}

3. 位运算解法

总共有 1<<n 个子集，mask每一位标记是否选取下标i元素

rust

impl Solution {
pub fn subsets(nums: Vec) -> Vec<Vec> {
let n = nums.len();
let mut res = Vec::new();
for mask in 0…(1 << n) {
let mut cur = Vec::new();
for i in 0…n {
if mask & (1 << i) != 0 {
cur.push(nums[i]);
}
}
res.push(cur);
}
res
}
}

复杂度

• 时间：O(n\cdot 2^n)，2n个子集，每个子集拷贝最多n个元素
• 空间：O(n) 回溯栈深度，输出集合不计入

测试调用

rust

fn main() {
let ans = Solution::subsets(vec![1,2,3]);
println!(“{:?}”, ans);
}

如果你需要，我直接输出 LeetCode 90 子集II（存在重复元素）Rust完整代码。