LeetCode 78. Subsets 解题报告

题目描述

Given a set of distinct integers, nums, return all possible subsets. .

示例

Example 1:

If nums = [1,2,3], a solution is:

[ [], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3] ]

注意事项

没有给出。

解题思路

我的思路：

这道题是一道很不错的题目，有很多种解法，所以很能锻炼思维和开阔思路。首先说一下我自己的解法。

这道题求的是集合的所有子集，在构造子集的时候，每一个元素都有两种选择，选或是不选，从而产生两个分支，不管是哪一种选择，都不影响下一个元素的决策，因此我使用了类似深搜的方式进行递归构造，在一次递归过程中，我都分别以不选和选两种状态进入下一个元素的递归调用，当所有元素都完成了决策时，就把产生的子集放入到结果中，整个过程非常直观，见下面我的代码。

参考思路：

虽然是很简单的题目，但是大神们给出了许多不同的解法，下面讲一下他们两种有趣的解法。

（1）第一种解法是用bitmap。对于n个元素，有

2n $2^n$ 个子集。对于每一个元素，都用一个bit表示选择与否，0表示不选，1表示选择。那么只用

0到2n−1 $0 到 2^n - 1$ 的数字就能表示所有的可能。举个例子：nums=[7,8]，最低位对应下标0的元素，依次类推，则

00 -> []

01 -> [7]

10 -> [8]

11 -> [7,8]

因此对于第i个bit，都判断其在各个数字中是否为1，即参考代码1中的if ((j >> i) & 1)，当为1时，就把第i个元素放入到相应数字对应的子集中。

具体实现见参考代码1。

（2）第二种解法让我很惊叹。它是发掘到了一个规律，集合中每添加一个元素，则子集数目增加一倍，且增加的子集为所有原始子集加上新的元素。举个例子：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。

因此，利用这个规律构建子集，实现过程见参考代码2。

代码

我的代码：

class Solution {public:    void dfs(vector
   
    
     > &res, vector
     
       &nums, vector
      
        temp, int i) {        if (i == nums.size()) {            res.push_back(temp);            return ;        }        dfs(res, nums, temp, i + 1);        temp.push_back(nums[i]);        dfs(res, nums, temp, i + 1);    }    vector
       
        
         > subsets(vector
         
          & nums) { vector
          
           
            > res; vector
            
              temp; dfs(res, nums, temp, 0); return res; }};

参考代码1：

class Solution {public:    vector
   
    
     > subsets(vector
     
      & nums) {        sort(nums.begin(), nums.end());        int elem_num = nums.size();        int subset_num = pow (2, elem_num);        vector
      
       
        > subset_set(subset_num, vector
        
         ()); for (int i = 0; i < elem_num; i++) for (int j = 0; j < subset_num; j++) if ((j >> i) & 1) subset_set[j].push_back(nums[i]); return subset_set; }};

参考代码2：

class Solution {public:    vector
   
    
     > subsets(vector
     
      & nums) {        vector
      
       
        > res(1, vector
        
         ()); for (int i = 0; i < nums.size(); i++) { int n = res.size(); for (int j = 0; j < n; j++) { res.push_back(res[j]); res.back().push_back(nums[i]); } } return res; }};

总结

这道题蛮简单的，关键是要通过不同的解法开阔自己的思路，做题最重要的不是AC，而是在于通过后进行总结反思。通过学习其他人的代码，我学到了很多小技巧，尽管不可能直接在其他题目上套用，但是会对其他题的思考有所启发。

这周就先完成这一道题目，得抓紧时间提高自己的综合能力，朝着自己的梦想前进，加油！

转载地址：http://qqntb.baihongyu.com/

你可能感兴趣的文章