Ang Li

Leetcode题解 78: Subsets

2020/04/05

题目内容

Given a set of distinct integers, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

题目样例

Input: nums = [1,2,3]
Output:
[
 [3],
 [1],
 [2],
 [1,2,3],
 [1,3],
 [2,3],
 [1,2],
 []
]

题目分析

首先我们需要搞清楚subsets的概念。

subsets指 子数组 不一定要连续

对于一个长为5的数组：

总长度为0的subsets共有img = 1

总长度为1的subsets共有img = 5

总长度为2的subsets共有 img = 10

总长度为3的subsets共有 img= 10

总长度为4的subsets共有 img= 5

总长度为5的subsets共有 img= 1

总共是1 + 5 + 10 + 5 + 1 = 32个子集，显而易见枚举法的时间复杂度为O(n * n)

采用深度优先遍历 记录每一个可能子数组

举例说明

nums = [1,2,3,4,5]

[]

[1]

[1, 2]

[1, 2, 3]

[1, 2, 3, 4]

[1, 2, 3, 4, 5]

[1, 2, 3, 5]

[1, 2, 4]

[1, 2, 4, 5]

[1, 2, 5]

[1, 3]

[1, 3, 4]

[1, 3, 4, 5]

[1, 3, 5]

[1, 4]

[1, 4, 5]

[1, 5]

[2]

[2, 3]

[2, 3, 4]

[2, 3, 4, 5]

[2, 4]

[2, 4, 5]

[2, 5]

[3]

[3, 4]

[3, 4, 5]

[3, 5]

[4]

[4, 5]

[5]

代码实现

Python

def dfs(self, start, S, result, father_subsets):
  	result.append(father_subsets)
  	for i in range(start, len(S)):
    		self.dfs(i+1, S, result, father_subsets+[S[i]])
    
def subsets(self, S):
    # none case
    if S is None:
      return []
      # deep first search
    result = []
    self.dfs(0, sorted(S), result, [])
    return result

注意事项

  1. 注意[] 也是子集之一
  2. 逐次加入一个数字，避免遗漏
  3. For循环找出下一层子集

复杂度

时间复杂度：O(n)

空间复杂度：O(n)

相似题目

Lintcode 15: Permutations

Post Directory