78. Subsets

Given a set of distinct integers, nums, return all possible subsets.

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

Solution: Recursive

class Solution(object):
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        subsets = []
        subset = []

        def dfs(start):
            subsets.append(subset[:])
            for idx in xrange(start, len(nums)):
                subset.append(nums[idx])
                dfs(idx + 1)
                subset.pop()

        dfs(0)
        return subsets

Solution: Iterative

class Solution(object):
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        subsets = [[]]
        for num in nums:
            for subset in subsets[:]:
                subsets.append(subset + [num])
        return subsets

Lessons:

• Since we are mutating subsets during iteration, use subsets[:] to make a copy first.

Related:

• 90. Subsets II