Subsets

78. Subsets

Example:

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

Solution 1: think from previous result

Say we already have the subsets of [1,2], now we add 3 .
The only thing we need to do is add 3 to every previous result.
That's it.

def subsets(self, nums):
    ret = [[]]
    for num in nums:
        if not ret:
            ret.append(num)
        else:
            length = len(ret)
            for i in xrange(length):
                ret.append(ret[i][:])
                ret[-1].append(num)
    return ret

Solution 2: DFS

For each number, it could form a subset with it's subsequence.
for nothing: []
for 1: [1], [1,2],[1,2,3]
for 2: [2], [2,3]
for 3: [3]

class Solution(object):
    def subsets (self, nums):
        res = []
        self.dfs(nums, 0, [], res)
        return res
    
    def dfs(self, nums, index, path, res):
        res.append(path)
        for i in xrange(index, len(nums)):
            self.dfs(nums, i+1, path+[nums[i]], res)

90. Subsets II 

Input could contains duplicates
Example: [1,2,2], [5,5,5]
Sort the list first, nums[i] == nums[i-1] if nums[i] has duplicates

for [1,2] subsets [], [1], [2], [1,2]
next we add another 2, we only need to add it to [2] and [1,2] 
which is the start point of previous 2.

for[5,5] subsets [], [5], [5,5]
next we add 5, we only need to add it to [5,5] 
which is the start point of previous 5.
def subsetsWithDup(self, nums):       
    ret = [[]]
    nums.sort()
    lastIdx = 0

    for k, num in enumerate(nums):
        length = len(ret)
        idx = 0
        if k != 0 and nums[k] == nums[k-1]:
            idx = lastIdx
        lastIdx = len(ret)
        for i in xrange(idx, length):
            ret.append(ret[i][:])
            ret[-1].append(num)
    return ret