Welcome to Subscribe On Youtube

Question

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

78. Subsets

Given a set of distinct integers, nums, return all possible subsets.

Note:
Elements in a subset must be in non-descending order.
The solution set must not contain duplicate subsets.

For example,
If nums = [1,2,3], a solution is:

[
  [],
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2]
]

@tag-array

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()
            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(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
    
    ############
    
    class Solution(object):
      def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: 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
    
    
  • 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