78. Subsets Medium

1/**
2 * [78] Subsets
3 *
4 * Given an integer array nums of unique elements, 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 * 
9 * Input: nums = [1,2,3]
10 * Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
11 * 
12 * Example 2:
13 * 
14 * Input: nums = [0]
15 * Output: [[],[0]]
16 * 
17 *  
18 * Constraints:
19 * 
20 * 1 <= nums.length <= 10
21 * -10 <= nums[i] <= 10
22 * All the numbers of nums are unique.
23 * 
24 */
25pub struct Solution {}
26
27// problem: https://leetcode.com/problems/subsets/
28// discuss: https://leetcode.com/problems/subsets/discuss/?currentPage=1&orderBy=most_votes&query=
29
30// submission codes start here
31
32impl Solution {
33    pub fn subsets(nums: Vec<i32>) -> Vec<Vec<i32>> {
34        let mut result: Vec<Vec<i32>> = Vec::new();
35        Self::dfs(&mut result, &mut vec![], &nums, 0);
36        result
37    }
38
39    fn dfs(result: &mut Vec<Vec<i32>>, current: &mut Vec<i32>, nums: &Vec<i32>, index: usize) {
40        if index == nums.len() {
41            result.push(current.clone());
42            return;
43        }
44        current.push(nums[index]);
45        Self::dfs(result, current, nums, index + 1);
46        current.pop();
47        Self::dfs(result, current, nums, index + 1);
48    }
49}
50
51// submission codes end
52
53#[cfg(test)]
54mod tests {
55    use super::*;
56
57    #[test]
58    fn test_78() {
59        println!("Got {:#?}", Solution::subsets(vec![1,2,3]));
60    }
61}
62