源網(wǎng)址：http://www.jianshu.com/p/ac57b9d3d211

原題

給定一個含不同整數(shù)的集合，返回其所有的子集

如果 S = [1,2,3]，有如下的解：

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

子集中的元素排列必須是非降序的，解集必須不包含重復(fù)的子集

解題思路

• Backtracking, DFS
• 首先，數(shù)組要排序，在第n層，加入一個元素進入n+1層，刪除剛剛加入的元素，加入第n層的第二個元素......

                                   [ ]
                                /   |                                [1]   [2]   [3]
                           /  |     |
                    [1, 2] [1, 3] [2, 3]
                      /
                [1, 2, 3]

完整代碼

# 方法一
class Solution(object):
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        if nums is None:
            return []
        res = [[]]
        self.dfs(sorted(nums), 0, [], res)
        return res

    def dfs(self, nums, index, path, res):
        for i in xrange(index, len(nums)):
            res.append(path + [nums[i]])
            path.append(nums[i])
            self.dfs(nums, i+1, path, res)
            path.pop()

# 方法二
class Solution(object):
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        if nums is None:
            return []
        res = [[]]
        self.dfs(sorted(nums), 0, [], res)
        return res

    def dfs(self, nums, index, path, res):
        for i in xrange(index, len(nums)):
            res.append(path + [nums[i]])
            self.dfs(nums, i+1, path+[nums[i]], res)

# 方法三
class Solution(object):
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        nums.sort()
        result = [[]]
        for x in nums:
            with_x = []
            for s in result:
                with_x.append(s + [x])
            result = result + with_x
    return result