LeetCode#78 Subsets

2017-08-31
#LeetCode #Python #Backtracking
程式解題/ LeetCode

問題

給一串元素相異的數列，求由此數列之元素所組成的所有子集合。

輸入

[1,2,3]

輸出

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

方法

每個元素可以出現或是不出現，每一種組合方法都是一個子集合，所以時間複雜度是O(2n) 。
利用Backtracking遞迴枚舉所有可能。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
    def subsets(self, nums):
        self.length = len(nums)
        self.ans = []
        self.backtrack(nums, [])
        return(self.ans)

    def backtrack(self, nums, n):
        if len(n) == self.length:
            a = [nums[i] for i, v in enumerate(n) if v]
            self.ans.append(a)
        else:
            self.backtrack(nums, n + [True])
            self.backtrack(nums, n + [False])

其他解法以及類似問題請看這裡。