78. 子集

发表于 | 分类于 | 阅读次数：

链接：https://leetcode-cn.com/problems/subsets/

题目描述

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

示例:

1
2
3
4
5
6
7
8
9
10
11
12
输入: nums = [1,2,3]
输出:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

分析

其实是非常简单的一个递归回溯的过程。
假设输入是1、2、3、4，递归的过程是：

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

而按照回溯的步骤去走一定是不会重复的。

综合答案为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution(object):
    def __init__(self):
        self.result_all = None
    
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        self.result_all = []
        self.dfs(nums, 0, 0, [])
        return self.result_all
        
    
    def dfs(self, nums, n, start, result):
        self.result_all.append(result[:])
        if len(nums) == n:
            return
        
        for i in range(start, len(nums)):
            result.append(nums[i])
            self.dfs(nums, n + 1, i + 1, result)
            result.pop()
        return