90. Subsets II Medium

1/**
2 * [90] Subsets II
3 *
4 * Given an integer array nums that may contain duplicates, return all possible subsets (the power set).
5 * The solution set must not contain duplicate subsets. Return the solution in any order.
6 *  
7 * Example 1:
8 * Input: nums = [1,2,2]
9 * Output: [[],[1],[1,2],[1,2,2],[2],[2,2]]
10 * Example 2:
11 * Input: nums = [0]
12 * Output: [[],[0]]
13 *  
14 * Constraints:
15 * 
16 * 1 <= nums.length <= 10
17 * -10 <= nums[i] <= 10
18 * 
19 */
20pub struct Solution {}
21
22// problem: https://leetcode.com/problems/subsets-ii/
23// discuss: https://leetcode.com/problems/subsets-ii/discuss/?currentPage=1&orderBy=most_votes&query=
24
25// submission codes start here
26
27impl Solution {
28    pub fn subsets_with_dup(nums: Vec<i32>) -> Vec<Vec<i32>> {
29        let mut result = vec![];
30        let mut d = nums.clone();
31        d.sort();
32        Self::dfs(&d, &mut result, &mut vec![], 0);
33        result
34    }
35
36    fn dfs(nums: &Vec<i32>, result:&mut Vec<Vec<i32>>, current: &mut Vec<i32>, index: usize) {
37        result.push(current.clone());
38        for i in index..nums.len() {
39            if i > index && nums[i] == nums[i - 1] {continue};
40            current.push(nums[i]);
41            Self::dfs(nums, result, current, i + 1);
42            current.pop();
43        }
44    }
45}
46
47// submission codes end
48
49#[cfg(test)]
50mod tests {
51    use super::*;
52
53    #[test]
54    fn test_90() {
55        println!("Got {:#?}", Solution::subsets_with_dup(vec![1,2,2]));
56    }
57}
58