78.md

78. Subsets

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

Note: 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],
  []
]

my thoughts:

1. dfs for a combination size from 0 to len(nums).

my solution:

**********66 ms
class Solution:
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        def dfs(nums, res, cur, l, start):
            if len(cur) == l:
                res.append(cur[:])
                return
            for i in range(start, len(nums)):
                cur.append(nums[i])
                dfs(nums, res, cur, l, i+1)
                cur.pop()
        res = []
        cur = []
        #dfs(nums, res, cur, 2, 0)
        for l in range(len(nums)+1):
            cur = []
            dfs(nums, res, cur, l, 0)
        return res

my comments:

from other ppl's solution:

1'. 55ms:
class Solution:
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        if not nums:
            return [[]]
        sub = self.subsets(nums[1:])
        return sub + [[nums[0]] + x for x in sub]  

1. pure math, 59ms:
class Solution:
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        ans = [[]]
        nums = sorted(nums)
        
        for i in nums:
            tmpans = ans[:]
            for l in ans:
                h = l[:]
                h.append(i)
                tmpans.append(h)
            ans = tmpans[:]
        return (ans)
2. 56ms:
class Solution:
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        out = [[]]
        
        for x in nums:
            tmp = []
            for subset in out:
                tmp.append(subset + [x])
            out.extend(tmp)
            
        return out