Leetcode 78: Subsets

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

Code (Bit manipulation)

class Solution(object):
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        ss_num = 2 ** len(nums)
        ss = [[] for i in xrange(ss_num)]

        for i in xrange(ss_num):
            k = i
            for j in xrange(len(nums)):
                if k & 1:
                    ss[i].append(nums[j])
                k = k >> 1
        return ss
                

Idea

There should be $latex 2^len(nums)$ subsets. So you can construct binary numbers from 0…0 to 1…1. For each binary number, its every bit indicates whether to includes a number in `nums`. 

Code (DFS)

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

Idea

Try to build a directed graph in which node x connects to node y (y > x). For example, if the given set is [0,1,2,3,4], then:
node 0 is connected to node 1, 2, 3, 4
node 1 is connected to node 2,3,4
node 2 is connected to node 3,4
node 3 is connected to node 4

Then you do dfs. At the moment of visiting each node, you add the traced path to result.