78. Subsets

Description of the Problem

Given an integer array nums of unique elements, return all possible subsets (the power set).

The solution set must not contain duplicate subsets. Return the solution in any order.

Example 1:

Input: nums = [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

Example 2:

Input: nums = [0]
Output: [[],[0]]

Constraints:

1 <= nums.length <= 10
-10 <= nums[i] <= 10
All the numbers of nums are unique.

Solution

Explanation

For any elements in a set, we have two options (Yes-No Question Method): either it is in the subset and it isn't in the subset.

Code (Rust)

impl Solution {
    pub fn subsets(mut nums: Vec<i32>) -> Vec<Vec<i32>> {
        return Self::dfs(&mut nums);
    }

    fn dfs(v : &mut Vec<i32> ) -> Vec<Vec<i32>> {
        if v.len() == 0 {
            return vec![vec![]];
        }else {
            let last = v
                .pop()
                .expect("Should have a number");
            
            // Set of set which does not contain the last element
            let mut no_comb = Self::dfs(v);

            // Set of set which **does** contain the last element
            let mut yes_comb = no_comb.clone();
            for set in yes_comb.iter_mut() {
                set.push(last);
            }

            // Combine into one
            no_comb.extend(yes_comb);
            return no_comb;
        }
    }
}

Complexity (n is the number of elements in the set)

Time complexity:

\( \Theta(n^2) \)
- Recursive Approach: \(T(n) = T(n - 1) + c \cdot (n-1) + c \cdot n\)

Auxiliary Space:

\( \Theta(n) \)
- \(n\) for stack calls

Leetbook