---
# System prepended metadata

title: 78 Subsets 筆記
tags: [78 Subsets]

---

###### tags: `78 Subsets`
# 78 Subsets 筆記

# 題目

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**.

**Constraints:**

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

**Example 1:**

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

```

**Example 2:**

```
Input: nums = [0]
Output: [[],[0]]
```

要把給的 nums 組合出所有可能的組合

題目說 nums 最少就 1 個，最多就 10，也就是說最多會有 10 個數字參加組合

nums[i] 的大小會限制在 -10~10之間，這條件不知道有什麼用，也許要省空間的話可以用較小的變數儲存？

不管排列順序，所以 [1, 2 ,3], [2, 3, 1] 都是一樣的

每個數字不會重複，所以也不用擔心一樣的數字組合成一樣的組合

# 整理規則

::: info
nums = [1]

0個數字的：[]

1個數字的： [1]
:::

::: info
nums = [1,2]

0個數字的：[]

1個數字的： [1], [<font color=#FF00>2</font>]

2個數字的：[1,<font color=#FF00>2</font>]
:::

:::info
nums = [1,2,3]

0個數字的：[]

1個數字的： [1], [2], [<font color=#FF00>3</font>]

2個數字的：[1,2], [1,<font color=#FF00>3</font>], [2,<font color=#FF00>3</font>]

3個數字的：[1,2,<font color=#FF00>3</font>]
:::

:::info
nums = [1,2,3,4]

0個數字的：[]

1個數字的： [1], [2], [3], [<font color=#FF00>4</font>]

2個數字的：[1,2], [1,3], [1,<font color=#FF00>4</font>], [2,3], [2,<font color=#FF00>4</font>], [3,<font color=#FF00>4</font>]

3個數字的：[1,2,3], [1,2,<font color=#FF00>4</font>], [1,3,<font color=#FF00>4</font>], [2,3,<font color=#FF00>4</font>]

4個數字的：[1,2,3,<font color=#FF00>4</font>]
:::

:::success
一個數字時可以看成 $C^1_0+C^1_1=1+1=2^1$

兩個數字時可以看成 $C^2_0+C^2_1+C^2_2=1+2+1=4=2^2$

三個數字時可以看成 $C^3_0+C^3_1 + C^3_2 + C^3_3 = 1+3 + 3 + 1 = 8=2^3$

四個數字時可以看成 $C^4_0+C^4_1+C^4_2+C^4_3+C^4_4=1+4+6+4+1=16=2^4$

五個數字時可以看成 $C^5_0+C^5_1+C^5_2+C^5_3+C^5_4+C^5_5=1+5+10+10+5+1=32=2^5$
:::

## 思路ㄧ：

寫一個 Combination(_ nums:[Int], _ n: Int) -> [Int]

n 代表要在 nums 取出多少個數字組合起來
return 取得組合起來的 array

n > 1 的話就先取出一個數字在把剩下的數字交給下一個Combination計算
ex: Combination([1,2,3], 2)
那就會在nums裡取出 1, 2, 3 各一次

寫出來後遇到較多的組合會超時

## 思路二：

經過上面從 1~4 的規則整理可以看出，4的組合就是在 3 的組合上把 4 再加上去而已，所以要

取得 4 個數字的組合就要先取得 3 個數字的組合

取得 3 個數字的組合就要先取得 2 個數字的組合

取得 2 個數字的組合就要先取得 1 個數字的組合

取得 1 個數字的組合就要先取得 0 個數字的組合

最基礎的條件是 0 個數字的組合就是 [ ]

我的想法是把 0, 1, 2, 3, 4, … 個數字的排列分別存到 Dictionary 裡面

這樣從 0 的組合開始，每加入一個數字就從個數最大的 Dictionary 裡面把組合都拿出來加上新的數字，然後放到對應個數的 Dictionary 裡，最後要取得答案的時候再把 Dictionary 的答案都放到 array 就完成了

---
[作業](https://github.com/GametreeRoger/LeetCode/blob/main/LeetCode78.playground/Contents.swift)