Welcome to Subscribe On Youtube

Question

Formatted question description: https://leetcode.ca/all/78.html

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.

Algorithm

For the example [1,2,3] given in the title,

  • it is an empty set at the beginning,
  • then we have to deal with 1, add 1 to the empty set, which is [1], and now we have two selves [] And [1],
  • let’s deal with 2, we add 2 to each of the previous subsets, and we can get [2], [1, 2], then all the subsets are now [], [1], [2], [1, 2],
  • in the same way, we can get [3], [1, 3], [2, 3], [1, 2, 3], plus all of previous the subsets
[]
[1]
[2]
[1 2]
[3]
[1 3]
[2 3]
[1 2 3]

Code

  • import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.List;
    
    public class Subsets {
    
        public class Solution {
            public List<List<Integer>> subsets(int[] nums) {
    
                List<List<Integer>> list = new ArrayList<>();
                if (nums == null || nums.length == 0) {
                    return list;
                }
    
                Arrays.sort(nums); // requirement: non-descending order
    
                // prepare, add empty one to start looping then.
                // @note: I forgot empty
                ArrayList<Integer> empty = new ArrayList<>();
                list.add(empty);
    
                for (int i = 0; i < nums.length; i++) {
                    int numToAdd = nums[i];
                    List<List<Integer>> newlyAddedList = new ArrayList<>(list);
    
                    for (List<Integer> each : list) {
                        ArrayList<Integer> newOne = new ArrayList<Integer>(each); // deep copy
    
                        newOne.add(numToAdd);
                        newlyAddedList.add(newOne);
    
                    }
    
                    list = newlyAddedList;
                }
    
                return list;
            }
        }
    
        class Solution_dfs {
    
            public List<List<Integer>> subsets(int[] nums) {
                List<List<Integer>> ans = new ArrayList<>();
                getAns(nums, 0, new ArrayList<>(), ans);
                return ans;
            }
    
            private void getAns(int[] nums, int start, ArrayList<Integer> temp, List<List<Integer>> ans) {
                ans.add(new ArrayList<>(temp)); // @note: deep copy
                for (int i = start; i < nums.length; i++) {
                    temp.add(nums[i]);
                    getAns(nums, i + 1, temp, ans);
                    temp.remove(temp.size() - 1);
                }
            }
        }
    
    }
    
    ############
    
    class Solution {
        private List<List<Integer>> ans = new ArrayList<>();
        private int[] nums;
    
        public List<List<Integer>> subsets(int[] nums) {
            this.nums = nums;
            dfs(0, new ArrayList<>());
            return ans;
        }
    
        private void dfs(int u, List<Integer> t) {
            if (u == nums.length) {
                ans.add(new ArrayList<>(t));
                return;
            }
            dfs(u + 1, t);
            t.add(nums[u]);
            dfs(u + 1, t);
            t.remove(t.size() - 1);
        }
    }
    
  • // OJ: https://leetcode.com/problems/subsets/
    // Time: O(N * 2^N)
    // Space: O(N)
    class Solution {
    public:
        vector<vector<int>> subsets(vector<int>& A) {
            vector<vector<int>> ans;
            vector<int> tmp;
            function<void(int)> dfs = [&](int i) {
                if (i == A.size()) {
                    ans.push_back(tmp);
                    return;
                }
                tmp.push_back(A[i]);
                dfs(i + 1); // Pick A[i]
                tmp.pop_back();
                dfs(i + 1); // Skip A[i]
            };
            dfs(0);
            return ans;
        }
    };
    
  • from typing import List
    
    class Solution: # bfs
        def subsets(self, nums: List[int]) -> List[List[int]]:
            if not nums:
                return [[]]
    
            nums.sort() # sort() not necessary if no duplicates
            result = [[]]
    
            for num in nums:
                result += [subset + [num] for subset in result]
    
            return result
    
    
    class Solution: # dfs
        def subsets(self, nums: List[int]) -> List[List[int]]:
            def dfs(u, t):
                ans.append(t[:]) # or, t.copy()
                for i in range(u, len(nums)):
                    t.append(nums[i])
                    dfs(i + 1, t)
                    t.pop()
    
            ans = []
            nums.sort() # sort() not necessary if no duplicates
            dfs(0, [])
            return ans
    
    
    class Solution: # dfs, just pass down the final path
        def subsets(self, nums: List[int]) -> List[List[int]]:
            def dfs(nums, index, path, ans):
                ans.append(path)
                [dfs(nums, i + 1, path + [nums[i]], ans) for i in range(index, len(nums))]
    
            ans = []
            dfs(nums, 0, [], ans)
            return ans
    
    
    class Solution: # dfs, but running slower, since need to reference from parent method for 'nums' and 'ans'
        def subsets(self, nums: List[int]) -> List[List[int]]:
            def dfs(index, path):
                ans.append(path)
                [dfs(i + 1, path + [nums[i]]) for i in range(index, len(nums))]
    
            ans = []
            dfs(0, [])
            return ans
    
    
  • func subsets(nums []int) [][]int {
    	var ans [][]int
    	var dfs func(u int, t []int)
    	dfs = func(u int, t []int) {
    		if u == len(nums) {
    			ans = append(ans, append([]int(nil), t...))
    			return
    		}
    		dfs(u+1, t)
    		t = append(t, nums[u])
    		dfs(u+1, t)
    		t = t[:len(t)-1]
    	}
    	var t []int
    	dfs(0, t)
    	return ans
    }
    
  • function subsets(nums: number[]): number[][] {
        const n = nums.length;
        const t: number[] = [];
        const res: number[][] = [];
        const dfs = (i: number) => {
            if (i === n) {
                res.push([...t]);
                return;
            }
            dfs(i + 1);
            t.push(nums[i]);
            dfs(i + 1);
            t.pop();
        };
        dfs(0);
        return res;
    }
    
    
  • impl Solution {
        fn dfs(i: usize, t: &mut Vec<i32>, res: &mut Vec<Vec<i32>>, nums: &Vec<i32>) {
            if i == nums.len() {
                res.push(t.clone());
                return;
            }
            Self::dfs(i + 1, t, res, nums);
            t.push(nums[i]);
            Self::dfs(i + 1, t, res, nums);
            t.pop();
        }
    
        pub fn subsets(nums: Vec<i32>) -> Vec<Vec<i32>> {
            let mut res = Vec::new();
            Self::dfs(0, &mut Vec::new(), &mut res, &nums);
            res
        }
    }
    
    

All Problems

All Solutions