# 資訊

:::info
- Question: 78. Subsets
- From: Leetcode Daily Challenge 2024.05.21
- Difficulty: Medium
:::

---

# 目錄

:::info
[TOC]
:::

---

# 題目

Given an integer array `nums` of unique elements, return all possible subsets (the power set).
The solution set must not contain duplicate subsets. Return the solution in any order.

> Example 1:
:::success
* Input: `nums = [1,2,3]`
* Output: `[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]`
:::

> Example 2:
:::success
* Input: `nums = [0]`
* Output: `[[],[0]]`
:::

> Constraints:
:::success
* 1 <= `nums.length` <= 10
* -10 <= `nums[i]` <= 10
* All the numbers of nums are unique.
:::

---

# 解法

## 概念

久違沒刷 leetcode 了，因為晚上要考 CPE 多少碰一下

這次是之前看過的題目，就是給一個 array，找出他所有的 subset，不難，就是明顯的 backtracking 題目，但怎麼做比較麻煩

不用 bit manipulation 是因為懶的用了，覺得多加一些 bit 上去不會比較方便

概念是這樣的，一開始不管是誰都會有一個 subset 是空集合，所以預設答案是 `[[]]` 這樣，之後每一輪都會走訪一個元素，然會會把元素一一 append 到原本的 ans 中，當然原本的 ans 不能動到，因為那也是一個答案，所以會用 copy 的方式實作

原理就像把二進位數字寫出來看，假設有三個 bit，要描述所有情況就會像這樣列出來：

000
001
010
011
100
101
110
111

`000` 就是空集合，而可以看到，假設現在走訪最高 bit，其實就是把之前的情況複製下來，然後加上一輪有他的版本，跟這題的概念一模一樣，透過這個方法就可以很好的做到 backtracking 所有 subset

## 程式碼

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        ans = [ [] ]
        for i in range(len(nums)):
            tmp = copy.deepcopy(ans)
            for j in range(len(tmp)):
                tmp[j].append(nums[i])
            for j in range(len(tmp)):
                ans.append(tmp[j])
        return ans

---

# 複雜度

## 時間複雜度

基本上是列舉所有情況了，所以會是 $O(2^n)$


## 空間複雜度

空間也差不多，就是要儲存解答的空間，所以也是 $O(2^n)$