子集

這道題求子集，集合的基本運算之一，按照高中數學學習集合的知識，可以把這個找冪集的過程按照元素的個數來劃分步驟。也就是先找零個元素的子集，再找一個元素的子集，再找兩個元素的子集...一直到找N個元素的集合為止。

我的第一想法是對找k個元素的集合這個過程使用回溯的方法。

回溯三部曲：

• 返回值void，參數startIndex
• 終止條件：找到n個數就可結束
• 當層函數邏輯循環
  • 橫向循環：從startIndex開始往后依次遍歷，作為當前輪的所有可能
  • 縱向迭代：startIndex層的數的下一個數作為迭代的下一層起點

代碼(執行用時擊敗35.31%，消耗內存擊敗17.38%)：

class Solution {
vector<vector<int>> ans;
vector<int> path;
void backtrack(vector<int> nums,int len,int startIndex){if(path.size()==len){//終止條件ans.push_back(path);return;}for(int i = startIndex;i<nums.size();i++){//當前輪的循環path.push_back(nums[i]);backtrack(nums,len,i+1);//下一層的迭代path.pop_back();}
}
public:vector<vector<int>> subsets(vector<int>& nums) {for(int k = 0;k<=nums.size();k++){//子集元素的數量從0到|S|backtrack(nums,k,0);}return ans;}
};

感覺自己的時間和空間消耗還是比較糟糕，參考代碼隨想錄的做法，發現原來可以不用這樣劃分子集的長度。因為求冪集的遞歸-回溯過程是寬度為集合長度，高度為集合長度的一棵樹。如下圖：

代碼也省去對子集中元素個數的一一羅列，代碼執行時間擊敗33.87%，消耗內存擊敗42.94%。竟然在時間消耗上更低了。

class Solution {
private:vector<vector<int>> result;vector<int> path;void backtracking(vector<int>& nums, int startIndex) {result.push_back(path); // 收集子集，要放在終止添加的上面，否則會漏掉自己if (startIndex >= nums.size()) { // 終止條件可以不加return;}for (int i = startIndex; i < nums.size(); i++) {path.push_back(nums[i]);backtracking(nums, i + 1);path.pop_back();}}
public:vector<vector<int>> subsets(vector<int>& nums) {result.clear();path.clear();backtracking(nums, 0);return result;}
};

這道題和之前的回溯不一樣的地方在于，所有的樹節點都是答案的一種情況，而之前的答案都是在葉子節點也就是滿足終止條件的時候。求集合冪集的方法可以無需設置終止條件。

子集II

這道題是在上面第一道題基礎上加上一個去重的操作，也就是第一次遇到元素時正常執行，但是第二次遇到相同的元素，則需要跳過。

代碼如下：

class Solution {
vector<vector<int>> ans;
vector<int> path;
void backtrack(vector<int> nums,int startIndex){ans.push_back(path);//沒有終止條件for(int i = startIndex;i<nums.size();i++){//當前層的循環if(i>startIndex && nums[i]==nums[i-1]){//不重復執行continue;}path.push_back(nums[i]);backtrack(nums,i+1);//遞歸調用下一層的函數path.pop_back();//回溯}
}
public:vector<vector<int>> subsetsWithDup(vector<int>& nums) {sort(nums.begin(),nums.end());//為了把集合中相同的元素集中到一起，需要排序backtrack(nums,0);return ans;}
};

寫這一題代碼的時候，我在for循環中使用continue，以為continue是直接從if跳到循環條件判斷的地方，所以在continue前還加上了i++，導致我的代碼過了給出的測試但沒有AC。原來for循環中的contimue是跳轉到i++這個循環變量遞變的位置。