Last Updated on 2022-02-13 by Clay
題目
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:
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]]
Constraints:
1 <= nums.length <= 10-10 <= nums[i] <= 10- All the numbers of
numsare unique.
題目給定一組陣列，我們則要窮舉出所有可能的子組合並回傳。
解題思路
一開始我嘗試使用遞迴去展開，但後來發現使用位元操作來計算似乎更直覺些。
比方說 Example 1 給了 [1, 2, 3] 這樣的輸入，那麼我們可以想像成二進制來窮組所有的組合，只要對應位置為 1 則代表要取該值。
0: 000 => []
1: 001 => [1]
2: 010 => [2]
3: 011 => [1, 2]
4: 100 => [3]
5: 101 => [1, 3]
6: 110 => [2, 3]
7: 111 => [1, 2, 3]
這樣一來，答案數量我們也提前知道了，那就是 2 ^ nums 長度。
C++ 範例程式碼
class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
// Init
int len = nums.size();
vector<vector<int>> results;
// Insert the answer
for (int i=0; i<(1<<len); ++i) {
int bits = i;
vector<int> temp;
for (int j=0; j<nums.size(); ++j) {
if (bits & 1 == 1) {
temp.push_back(nums[j]);
}
bits = bits >> 1;
}
results.push_back(temp);
}
return results;
}
};Python 範例程式碼
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
# Init
numsLen = len(nums)
results = []
# Insert the answer
for i in range(1<<numsLen):
bits = i
temp = []
for j in range(numsLen):
if (bits & 1 == 1):
temp.append(nums[j])
bits = bits >> 1;
results.append(temp)
return results