78.Subsets

Tags: [subset], [recursion], [brute_force], [combination]

Com: {fb}

Link: https://leetcode.com/problems/subsets/\#/description

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

Note:The solution set must not contain duplicate subsets.

For example,
Ifnums=[1,2,3], a solution is:

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

Solution: Brute Force, Combination

class Solution(object):
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        if not nums:
            return [[]]

        result = [[]]
        buff = []
        self.subsets_helper(nums, 0, buff, result)
        return result

    def subsets_helper(self, nums, index, buff, result):
        for i in xrange(index, len(nums)):
            buff.append(nums[i])
            result.append(list(buff))
            self.subsets_helper(nums, i + 1, buff, result)
            buff.pop()

Revelation:

• Don't forget the empty array [] is one of the necessary subset.

Note:

• Time complexity = O(n!), n is the number of the elements of the given arrays. Because we want to collect all subsets, from the math, if given n elements, there are O(n!) subsets.
• Space complexity = O(n), here we don't calculate the space used to store the result. The depth of the recursion is O(n), is the max size of the buff is O(n).