leetcode/
subsets.rs

1//! # 78. 子集
2//!
3//! 难度 中等
4//!
5//! 给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
6//!
7//! 说明：解集不能包含重复的子集。
8//!
9//! ## 示例:
10//!
11//! ```text
12//! 输入: nums = [1,2,3]
13//! 输出:
14//! [
15//!   [3],
16//!   [1],
17//!   [2],
18//!   [1,2,3],
19//!   [1,3],
20//!   [2,3],
21//!   [1,2],
22//!   []
23//! ]
24//! ```
25//!
26//! See [leetcode](https://leetcode-cn.com/problems/subsets/)
27//! and [more](https://leetcode-cn.com/problems/subsets/solution/rust-1-xing-dai-ma-gao-jie-han-shu-han-s-2gl2/)
28
29pub struct Solution;
30
31impl Solution {
32    pub fn subsets(nums: Vec<i32>) -> Vec<Vec<i32>> {
33        (0..(1 << nums.len())).map(|mask| {
34            nums.iter().enumerate()
35                // or use one `filter_map`
36                .map(|(i, v)| (mask & (1 << i), v))
37                .filter(|(i, _)| *i != 0)
38                .map(|(_, &v)| v)
39                .collect()
40        }).collect()
41    }
42}
43
44// let mut ans = Vec::new();
45// backtrack(&nums[..], &mut vec![], &mut ans);
46// ans
47fn backtrack(nums: &[i32], subset: &mut Vec<i32>, ans: &mut Vec<Vec<i32>>) {
48    if nums.len() == 0 {
49        ans.push(subset.clone());
50        return;
51    }
52    subset.push(nums[0]);
53    backtrack(&nums[1..], subset, ans);
54    subset.pop();
55    backtrack(&nums[1..], subset, ans);
56}
57
58// producer(&nums).collect()
59fn producer<'a>(nums: &'a [i32]) -> impl Iterator<Item = Vec<i32>> + 'a {
60    (0..(1 << nums.len())).map(move |mask| {
61        nums.iter().enumerate().filter_map(|(i, &v)| {
62            if mask & (1 << i) != 0 {
63                Some(v)
64            } else {
65                None
66            }
67        }).collect()
68    })
69}
70
71#[cfg(test)]
72mod tests {
73    use super::*;
74
75    #[test]
76    fn test() {
77        let cases: Vec<(Vec<i32>, Vec<Vec<i32>>)> = vec![
78            (vec![1,2,3], vec![
79                vec![3],
80                vec![1],
81                vec![2],
82                vec![1,2,3],
83                vec![1,3],
84                vec![2,3],
85                vec![1,2],
86                vec![]
87            ]),
88        ];
89
90        for (nums, mut expect) in cases {
91            expect.sort();
92            let mut ans = Solution::subsets(nums);
93            ans.sort();
94            assert_eq!(expect, ans);
95        }
96    }
97}
leetcode/subsets.rs

leetcode/
subsets.rs
