Leetcode 78.子集

Posted on |

78.子集

题目

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
示例:

输入: nums = [1,2,3]
输出:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

方法

方法1：回溯法

设n = len(nums)，那么这个问题可以考虑为n叉树，对这个树进行dfs，这个问题里的回溯点就是start=len(nums)时

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution(object):
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        ans=[]
        self.backtrack(nums,ans,[],0)
        return ans

    def backtrack(self,nums,ans,tmp,start):
        ans.append(list(tmp))
        for i in range(start,len(nums)):
            tmp.append(nums[i])
            self.backtrack(nums,ans,tmp,i+1)
            tmp.pop()

# backtrack([1, 2, 3], [], [], 0)
# backtrack([1, 2, 3], [[]], [1], 1)
# backtrack([1, 2, 3], [[], [1]], [1, 2], 2)
# backtrack([1, 2, 3], [[], [1], [1, 2]], [1, 2, 3], 3)
# --------------------
# pop:  3
# --------------------
# pop:  2
# backtrack([1, 2, 3], [[], [1], [1, 2], [1, 2, 3]], [1, 3], 3)
# --------------------
# pop:  3
# --------------------
# pop:  1
# backtrack([1, 2, 3], [[], [1], [1, 2], [1, 2, 3], [1, 3]], [2], 2)
# backtrack([1, 2, 3], [[], [1], [1, 2], [1, 2, 3], [1, 3], [2]], [2, 3], 3)
# --------------------
# pop:  3
# --------------------
# pop:  2
# backtrack([1, 2, 3], [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3]], [3], 3)
# --------------------
# pop:  3
# --------------------
# [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]