[LeetCode] Challenge log 78

Posted on |
78. Subsets

Alg1: DFS.

Alg2: For each node there is only two choice, include or exclude. Build all the powerset sumoutenously using list comprehension.

Given a set of distinct integers, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

1
2
3
4
5
6
7
8
9
10
11
12
Input: nums = [1,2,3]
Output:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]
Soulution:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# Alg1
class Solution:
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        n = len(nums)
        if n == 0:
            return []
        
        def dfs(nums, i, st):
            if i == n: 
                res.append(st)
                return
            dfs(nums, i+1, st)
            dfs(nums, i+1, st + [nums[i]])
        
        res = []
        dfs(nums, 0 , [])
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# Alg2
class Solution:
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        n = len(nums)
        if n == 0:
            return []
        elif n == 1:
            return [nums, []]
        else:
            res = [[]]
            for num in nums:
                res += [x + [num] for x in res]
            return res
0%