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] 都是一樣的

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

整理規則

nums = [1]

0個數字的：[]

1個數字的： [1]

nums = [1,2]

0個數字的：[]

1個數字的： [1], [2]

2個數字的：[1,2]

nums = [1,2,3]

0個數字的：[]

1個數字的： [1], [2], [3]

2個數字的：[1,2], [1,3], [2,3]

3個數字的：[1,2,3]

nums = [1,2,3,4]

0個數字的：[]

1個數字的： [1], [2], [3], [4]

2個數字的：[1,2], [1,3], [1,4], [2,3], [2,4], [3,4]

3個數字的：[1,2,3], [1,2,4], [1,3,4], [2,3,4]

4個數字的：[1,2,3,4]

一個數字時可以看成

$C_0^1+C_1^1=1+1=2^1$

兩個數字時可以看成

$C_0^2+C_1^2+C_2^2=1+2+1=4=2^2$

三個數字時可以看成

$C_0^3+C_1^3+C_2^3+C_3^3=1+3+3+1=8=2^3$

四個數字時可以看成

$C_0^4+C_1^4+C_2^4+C_3^4+C_4^4=1+4+6+4+1=16=2^4$

五個數字時可以看成

$C_0^5+C_1^5+C_2^5+C_3^5+C_4^5+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 就完成了

---

作業