LeetCode78_子集（三種解法）

1. 題目

給你一個整數數組 nums ，數組中的元素 互不相同 。傳回該數組所有可能的子集（幂集）。

解集 不能 包含重複的子集。你可以按 任意順序 傳回解集。

示例 1：
輸入：nums = [1,2,3]
輸出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

示例 2：
輸入：nums = [0]
輸出：[[],[0]]
 
提示：
1 <= nums.length <= 10
-10 <= nums[i] <= 10
nums 中的所有元素 互不相同
           

2. 題解

# 78
from typing import List
import copy


class Solution:
    # 方法1： 擴充法
    def subsets_1(self, nums: List[int]) -> List[List[int]]:
        result = []
        result.append([])
        for n in nums:
            temp = []
            for res in result:
                r = copy.deepcopy(res)
                r.append(n)
                temp.append(r)

            for t in temp:
                result.append(t)
        return result

    # 方法2： 回溯法
    def subsets_2(self, nums: List[int]) -> List[List[int]]:
        result = []
        result.append([])
        for i in range(1, len(nums) + 1):
            self.backtracking(nums, result, i, 0, [])   # i 表示數組長度, index 表示目前序号
        return result

    def backtracking(self, nums, result, length, index, subset):
        if len(subset) == length:
            temp = copy.deepcopy(subset)
            result.append(temp)
            return

        for i in range(index, len(nums)):
            subset.append(nums[i])
            self.backtracking(nums, result, length, i + 1, subset)
            subset.pop()

    # 方法3： 分治法
    def subsets_3(self, nums: List[int]) -> List[List[int]]:
        result = []
        self.dfs(nums, result, 0, [])
        return result

    def dfs(self, nums, result, index, subset):
        result.append(copy.deepcopy(subset))
        if index == len(nums):
            return

        for i in range(index, len(nums)):
            subset.append(nums[i])
            self.dfs(nums, result, i + 1, subset)
            subset.pop()