leetcode 78題 子集（c++ 三種解法）

題目描述：

給定一組不含重複元素的整數數組 nums，傳回該數組所有可能的子集（幂集）。

說明：解集不能包含重複的子集。

示例:

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

解題思路：

解題思路1（包含三種解題方法）：這個我沒看懂作者本人的解題思路，沒看懂樹是怎麼建的

https://blog.csdn.net/camellhf/article/details/73551410

是以找到了解題思路2：是對解題思路1中作者的想法的一個詳細講解

https://www.cnblogs.com/ariel-dreamland/p/9154503.html

建立的樹是這樣的：（來源于第二個連結）

[]
                     /      \
                    /        \
                   /          \        
                  /            \     
                 /              \
              [1]                []
           /       \           /    \
          /         \         /      \        
       [1 2]       [1]       [2]     []
      /     \     /   \     /   \    / \
  [1 2 3] [1 2] [1 3] [1] [2 3] [2] [3] []
           

第一層為空集，第二層為對第一個數的選擇，以此類推。左節點代表選中，右節點代表不選。

代碼：

方法1：用dfs解決，對應解題思路1的第一個方法

注意的點：

1.每次一個數字出棧就相當于選擇了不選擇它的路。

2.為什麼從第一層開始循環？因為根節點不存在不選擇它的情況。

3.為什麼不需要存儲不選擇的情況？因為在存儲上一層節點值的時候，實際上就是在存儲不選擇的情況，因為沒到下一層相當于沒選擇。

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> result;
        vector<int> tmp;
        //sort(nums.begin(), nums.end());
        getSub(nums,result,0,tmp);
        return result;
    }
    void getSub(vector<int> s,vector<vector<int>> &result,int layer,vector<int> &tmp)
    {
        result.push_back(tmp);
        for(int i = layer;i < s.size();i++)
        {
            tmp.push_back(s[i]);
            getSub(s,result,i + 1,tmp);
            tmp.pop_back();
        }
    }
    
};
           

方法2：用bitmap解決，對應解題思路1的第二個方法

感覺原連結中的代碼寫的非常棒！

外層循環控制對數組中每個數字的選擇，内層循環是從二進制數000到111所有情況的列舉。

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        
        int bNumber = pow(2,nums.size()); //把二進制數轉化為十進制 為2^nums.size() 
        vector<vector<int>> result(bNumber);
        for(int i = 0;i < nums.size();i++)
            for(int j = 0;j < bNumber;j++)
                if(j >> i & 1) //j左移i位（進而判斷數組中第i個元素是否加入子集），結果和1相與（進而隻取最低位）
                    result[j].push_back(nums[i]);
        return result;
    }
    
};
           

方法3：對應解題思路1的第三個方法

即：

第二種解法讓我很驚歎。它是發掘到了一個規律，集合中每添加一個元素，則子集數目增加一倍，且增加的子集為所有原始子集加上新的元素。舉個例子：nums=[1,2,3] 

1. 初始時集合為空，子集為[ [] ]。 

2. 添加一個元素1,即集合為[1]時，子集為空集和空集+元素1，即[ [], [1] ]。 

3. 添加下一個元素2，集合為[1,2]，子集除了包含上一步的所有集合還新增了對應集合+元素2的所有集合，即[ [], [1], [2], [1,2]]，其中[2]是空集+元素2，[1,2]是[1]+元素2。 

4. 添加下一個元素3，集合為[1,2,3]，類似的得到子集為[ [], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3] ]，其中[3]是空集+元素3，[1,3]是[1]+元素3，[2,3]是[2]+元素3，[1,2,3]是[1,2]+元素3。

（來源于第一個連結）

class Solution {
public:
	vector<vector<int>> subsets(vector<int>& nums) {
		vector<vector<int>> result;
		vector<int> empty;
		result.push_back(empty);
		for (int i = 0; i < nums.size(); i++)
		{
			int result_size = result.size();//進入循環前存儲在添加前的結果長度 因為添加後長度會變
			for (int j = 0; j < result_size; j++)
			{
				vector<int> tmp = result[j];
                tmp.push_back(nums[i]);
                result.push_back(tmp);
			}
		}
		return result;
	}

};