LeetCode | 0078. Subsets子集【Python】

╰半橙微兮° 2022-12-18 01:00 111阅读 0赞

### Problem ###

[LeetCode][]

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

**Note:** The solution set must not contain duplicate subsets.

**Example:**

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

### 问题 ###

[力扣][Link 1]

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

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

**示例:**

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

### 思路 ###

**回溯**

也是稍微改造一下 labuladong 的回溯模板就行。

##### Python3 代码 #####

from typing import List
    
    class Solution:
        def subsets(self, nums: List[int]) -> List[List[int]]:
            res = []
            n = len(nums)
    
            def backtrack(nums, start, path):
                # 加入 path
                res.append(path)
                # i 从 start 开始递增
                for i in range(start, n):
                    # 回溯及更新 path
                    # path.append([nums[i]])
                    backtrack(nums, i + 1, path + [nums[i]])
                    # path.pop()
            
            backtrack(nums, 0, [])
            return res

有一点疑惑，回溯更新 path 那里使用如下代码就运行不出正确结果，暂时还没找到原因：

for i in range(start, n):
        # 回溯及更新 path
        path.append(nums[i])
        backtrack(nums, i + 1, path)
        path.pop()

### GitHub 链接 ###

[Python][]

[LeetCode]: https://leetcode.com/problems/subsets/
[Link 1]: https://leetcode-cn.com/problems/subsets/
[Python]: https://github.com/Wonz5130/LeetCode-Solutions/blob/master/solutions/0078-Subsets/0078.py