給一個array,返回這個array能組成的所有子集合(Subsets)
Python
從空開始,每個之前結果的子集加新的num
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
res = [[]]
for num in nums:
res += [item+[num] for item in res]
return res
遞歸法 :
class Solution:
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
res=[]
self.dfs(nums,0,res,path)
return res
def dfs(self,nums,index,res,path):
res.append(path)
for i in range(index,len(nums)):
self.dfs(nums,i+1,res,path+[nums[i]])
C++
這個題目可以使用 DFS(深度優先搜索)的方法來解決。具體來說,我們可以從空集開始,依次枚舉原數組中的每個元素,對於每個元素,有兩種選擇:選擇它,或者不選擇它。如果選擇它,我們將它添加到當前集合中,並以此為基礎繼續遞歸;如果不選擇它,我們直接以當前集合為基礎繼續遞歸。當遞歸到原數組的最後一個元素時,我們就得到了一個新的子集。通過不斷地遞歸,我們可以枚舉出所有的子集。
在實現中,我們使用一個數組 path 來記錄當前集合,使用一個整數 index 來表示當前枚舉到的元素在原數組中的下標,使用一個二維數組 res 來存儲所有的子集。在每次遞歸開始時,我們將當前集合添加到 res 中;然後枚舉從 index 開始到原數組末尾的所有元素,對於每個元素,如果選擇它,我們將它添加到 path 中,並以此為基礎繼續遞歸;如果不選擇它,我們直接以 path 為基礎繼續遞歸。當遞歸結束後,我們需要將 path 中添加的最後一個元素刪除,以便回溯到上一層遞歸。
最後,我們返回二維數組 res,其中存儲了所有的子集。
class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>> res;
vector<int> path;
dfs(nums, 0, path, res);
return res;
}
private:
void dfs(const vector<int>& nums, int index, vector<int>& path, vector<vector<int>>& res) {
res.push_back(path);
for (int i = index; i < nums.size(); ++i) {
path.push_back(nums[i]);
dfs(nums, i + 1, path, res);
path.pop_back();
}
}
};