78. 子集

題目描述

給你一個整數數組 nums ，數組中的元素 互不相同 。返回該數組所有可能的子集（冪集）。

解集 不能 包含重復的子集。你可以按 任意順序 返回解集。

示例 1：

輸入：nums = [1,2,3]
輸出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

示例 2：

輸入：nums = [0]
輸出：[[],[0]]

提示：

• 1 <= nums.length <= 10
• -10 <= nums[i] <= 10
• nums 中的所有元素 互不相同

回溯算法

// 78. 子集
class Solution {
public:// 主函數，接受一個整數數組作為輸入，返回該數組所有可能的子集vector<vector<int>> subsets(vector<int>& nums) {backstracking(nums, 0);  // 開始回溯算法，從索引0開始return result;  // 返回所有找到的子集}private:vector<vector<int>> result;  // 用于存儲所有可能的子集vector<int> path;  // 用于存儲當前路徑（即當前構造的子集）// 回溯函數void backstracking(vector<int>& nums, int start) {// 每次進入函數，先將當前路徑添加到結果中// 因為子集也包括空集和包含部分元素的集合result.push_back(path);// 如果start等于nums的大小，說明已經處理完所有元素，返回if(start == nums.size()) {return;}// 從start開始遍歷nums中的每個元素for(int i = start; i < nums.size(); i++) {// 將當前元素添加到路徑中path.push_back(nums[i]);// 遞歸調用，i+1為下一次遞歸的起點backstracking(nums, i + 1);// 回溯：從路徑中移除剛才添加的元素，嘗試下一個元素path.pop_back();}}
};

這段代碼實現了一個經典的回溯算法框架，用于解決子集生成問題。它首先定義了一個result變量來存儲所有可能的子集，以及一個path變量來存儲當前正在構建的子集。backstracking是一個遞歸函數，它試圖通過遍歷數組nums的每個元素，并在每一步中決定是否將當前元素加入到當前路徑path中，從而構建出所有可能的子集。

關鍵點在于，每次進入backstracking函數時，無論當前路徑path的內容如何，都將其添加到結果集result中。這確保了包括空集在內的所有子集都被收集。然后，通過遞歸地調用自身并逐步增加start參數，算法確保每個元素都有機會被包括在子集中，同時避免了重復。最后，通過在每次遞歸后從path中移除最近添加的元素，這個算法能夠回溯并探索所有可能的子集組合。