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], [2] 2個數字的：[1,2] ::: :::info nums = [1,2,3] 0個數字的：[] 1個數字的： [1], [2], [3] 2個數字的：[1,2], [1,3], [2,3] 3個數字的：[1,2,3] ::: :::info 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] ::: :::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)