78. 子集 （點擊查看題目）
題目描述
給定一組 不含重複元素 的整數數組 nums，返回該數組所有可能的子集（冪集）。
說明：解集不能包含重複的子集。
示例:
<code>輸入: nums = [1,2,3]
輸出:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]/<code>
解決方案
觀察全排列 / 組合 / 子集問題，它們比較相似，且可以使用一些通用策略解決。
首先，它們的解空間非常大：
- 全排列：N！
- 組合：N！
- 子集：2^N，每個元素都可能存在或不存在。
在它們的指數級解法中，要確保生成的結果 完整 且 無冗餘，有三種常用的方法：
- 遞歸
- 回溯
- 基於二進制位掩碼和對應位掩碼之間的映射字典生成排列 / 組合 / 子集
相比前兩種方法，第三種方法將每種情況都簡化為二進制數，易於實現和驗證。
此外，第三種方法具有最優的時間複雜度，可以生成按照字典順序的輸出結果。
方法一：遞歸
思路
開始假設輸出子集為空，每一步都向子集添加新的整數，並生成新的子集。
Python 實現（可在電腦端查看代碼）
<code>class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
n = len(nums)
output = [[]]
for num in nums:
output += [curr + [num] for curr in output]
return output/<code>
Java 實現（可在電腦端查看代碼）
<code>class Solution {
public List<list>> subsets(int[] nums) {
List<list>> output = new ArrayList();
output.add(new ArrayList<integer>());
for (int num : nums) {
List<list>> newSubsets = new ArrayList();
for (List<integer> curr : output) {
newSubsets.add(new ArrayList<integer>(curr){{add(num);}});
}
for (List<integer> curr : newSubsets) {
output.add(curr);
}
}
return output;
}
}/<integer>/<integer>/<integer>/<list>/<integer>/<list>/<list>/<code>複雜度分析
時間複雜度：O(N × 2^N )，生成所有子集，並複製到輸出結果中。
空間複雜度：O(N × 2^N )，這是子集的數量。
對於給定的任意元素，它在子集中有兩種情況，存在或者不存在（對應二進制中的 0 和 1）。因此，N 個數字共有 2^N 個子集。
方法二：回溯
算法
冪集是所有長度從 0 到 n 所有子集的組合。
根據定義，該問題可以看作是從序列中生成冪集。
遍歷 子集長度，通過 回溯 生成所有給定長度的子集。
回溯法是一種探索所有潛在可能性找到解決方案的算法。如果當前方案不是正確的解決方案，或者不是最後一個正確的解決方案，則回溯法通過修改上一步的值繼續尋找解決方案。
算法
定義一個回溯方法 backtrack(first, curr)，第一個參數為索引 first，第二個參數為當前子集 curr。
- 如果當前子集構造完成，將它添加到輸出集合中。
- 否則，從 first 到 n 遍歷索引 i。
- 將整數 nums[i] 添加到當前子集 curr。
- 繼續向子集中添加整數：backtrack(i + 1, curr)。
- 從 curr 中刪除 nums[i] 進行回溯。
Python 實現（可在電腦端查看代碼）
<code>class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
def backtrack(first = 0, curr = []):
# if the combination is done
if len(curr) == k:
output.append(curr[:])
for i in range(first, n):
# add nums[i] into the current combination
curr.append(nums[i])
# use next integers to complete the combination
backtrack(i + 1, curr)
# backtrack
curr.pop()
output = []
n = len(nums)
for k in range(n + 1):
backtrack()
return output/<code>
Java 實現（可在電腦端查看代碼）
<code>class Solution {
List<list>> output = new ArrayList();
int n, k;
public void backtrack(int first, ArrayList<integer> curr, int[] nums) {
// if the combination is done
if (curr.size() == k)
output.add(new ArrayList(curr));
for (int i = first; i < n; ++i) {
// add i into the current combination
curr.add(nums[i]);
// use next integers to complete the combination
backtrack(i + 1, curr, nums);
// backtrack
curr.remove(curr.size() - 1);
}
}
public List<list>> subsets(int[] nums) {
n = nums.length;
for (k = 0; k < n + 1; ++k) {
backtrack(0, new ArrayList<integer>(), nums);
}
return output;
}
}/<integer>/<list>/<integer>/<list>/<code>複雜度分析
時間複雜度：O(N × 2^N )，生成所有子集，並複製到輸出集合中。
空間複雜度：O(N × 2^N )，存儲所有子集，共 n 個元素，每個元素都有可能存在或者不存在。
方法三：字典排序（二進制排序） 子集
思路
該方法思路來自於 Donald E. Knuth。
將每個子集映射到長度為 n 的位掩碼中，其中第 i 位掩碼 nums[i] 為 1，表示第 i 個元素在子集中；如果第 i 位掩碼 nums[i] 為 0，表示第 i 個元素不在子集中。
例如，位掩碼 0..00（全 0）表示空子集，位掩碼 1..11（全 1）表示輸入數組 nums。
因此要生成所有子集，只需要生成從 0..00 到 1..11 的所有 n 位掩碼。
乍看起來生成二進制數很簡單，但如何處理左邊填充 0 是一個問題。因為必須生成固定長度的位掩碼：例如 001，而不是 1。因此可以使用一些位操作技巧：
Python 實現（可在電腦端查看代碼）
<code>nth_bit = 1 << n
for i in range(2**n):
# generate bitmask, from 0..00 to 1..11
bitmask = bin(i | nth_bit)[3:]/<code>
Java 實現（可在電腦端查看代碼）
<code>int nthBit = 1 << n;
for (int i = 0; i < (int)Math.pow(2, n); ++i) {
// generate bitmask, from 0..00 to 1..11
String bitmask = Integer.toBinaryString(i | nthBit).substring(1);/<code>
或者使用簡單但低效的迭代進行控制：
Python 實現（可在電腦端查看代碼）
<code>for i in range(2**n, 2**(n + 1)):
# generate bitmask, from 0..00 to 1..11
bitmask = bin(i)[3:]/<code>
Java 實現（可在電腦端查看代碼）
<code>for (int i = (int)Math.pow(2, n); i < (int)Math.pow(2, n + 1); ++i) {
// generate bitmask, from 0..00 to 1..11
String bitmask = Integer.toBinaryString(i).substring(1);/<code>算法
- 生成所有長度為 n 的二進制位掩碼。
- 將每個子集都映射到一個位掩碼數：位掩碼中第 i 位如果是 1 表示子集中存在 nums[i]，0 表示子集中不存在 nums[i]。
- 返回子集列表。
Python 實現（可在電腦端查看代碼）
<code>class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
n = len(nums)
output = []
for i in range(2**n, 2**(n + 1)):
# generate bitmask, from 0..00 to 1..11
bitmask = bin(i)[3:]
# append subset corresponding to that bitmask
output.append([nums[j] for j in range(n) if bitmask[j] == '1'])
return output/<code>
Java 實現（可在電腦端查看代碼）
<code>class Solution {
public List<list>> subsets(int[] nums) {
List<list>> output = new ArrayList();
int n = nums.length;
for (int i = (int)Math.pow(2, n); i < (int)Math.pow(2, n + 1); ++i) {
// generate bitmask, from 0..00 to 1..11
String bitmask = Integer.toBinaryString(i).substring(1);
// append subset corresponding to that bitmask
List<integer> curr = new ArrayList();
for (int j = 0; j < n; ++j) {
if (bitmask.charAt(j) == '1') curr.add(nums[j]);
}
output.add(curr);
}
return output;
}
}/<integer>/<list>/<list>/<code>複雜度分析
時間複雜度：O(N × 2^N )，生成所有的子集，並複製到輸出列表中。
空間複雜度：O(N × 2^N )，存儲所有子集，共 n 個元素，每個元素都有可能存在或者不存在。
閱讀更多 力扣LeetCode 的文章
