Leetcode 78. Subsets - 程程下班學

給一個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();
        }
    }
};

Python

C++

相關