leetcode/
subsets_ii.rs

1//! # 90. 子集 II
2//!
3//! 难度 中等
4//!
5//! 给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
6//!
7//! 说明：解集不能包含重复的子集。
8//!
9//! ## 示例:
10//!
11//! ```text
12//! 输入: [1,2,2]
13//! 输出:
14//! [
15//!   [2],
16//!   [1],
17//!   [1,2,2],
18//!   [2,2],
19//!   [1,2],
20//!   []
21//! ]
22//! ```
23//!
24//! See [leetcode](https://leetcode-cn.com/problems/subsets-ii/)
25
26pub struct Solution;
27
28impl Solution {
29
30    /// 回溯法
31    pub fn subsets_with_dup(nums: Vec<i32>) -> Vec<Vec<i32>> {
32        let mut nums = nums;
33        nums.sort();
34        let mut ans = Vec::new();
35
36        backtrack(&nums[..], &mut vec![], &mut ans);
37        ans
38    }
39}
40
41fn backtrack(nums: &[i32], v: &mut Vec<i32>, ans: &mut Vec<Vec<i32>>) {
42    ans.push(v.clone());
43    for i in 0..nums.len() {
44        if i > 0 && nums[i] == nums[i - 1] {
45            continue;
46        }
47
48        v.push(nums[i]);
49        backtrack(&nums[(i + 1)..], v, ans);
50        v.pop();
51    }
52}
53
54#[cfg(test)]
55mod tests {
56    use super::*;
57
58    #[test]
59    fn test() {
60        let cases: Vec<(Vec<i32>, Vec<Vec<i32>>)> = vec![
61            (vec![1,2,2], vec![
62                vec![2],
63                vec![1],
64                vec![1,2,2,],
65                vec![2,2],
66                vec![1,2],
67                vec![],
68            ]),
69        ];
70
71        for (nums, mut expect) in cases {
72            let mut ans = Solution::subsets_with_dup(nums);
73            ans.sort();
74            expect.sort();
75            assert_eq!(expect, ans);
76        }
77    }
78}
leetcode/subsets_ii.rs

leetcode/
subsets_ii.rs
