Leetcode 78 Subsets

triplebee

发布于 2018-01-12 15:01:36

4410

发布于 2018-01-12 15:01:36

文章被收录于专栏：计算机视觉与深度学习基础

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

Note: The solution set must not contain duplicate subsets.

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

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

求出给定集合的所有子集。

先贴上我的迭代深搜

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

DFS可以做，但是看到这题有更新颖的做法，

将集合中包含的数用二进制表示，1表示有，0表示没有，总共需要遍历2^n次。

class Solution {  
public:  
    vector<vector<int> > subsets(vector<int> &S) {  
        vector< vector<int> > result;  
        sort(S.begin(), S.end());  
        // Loop from 0 to 2^n - 1  
        for (int x = 0; x < (1 << S.size()); ++x) {  
            vector<int> sln;  
            for (int i = 0; i < S.size(); ++i)  
                // If the i-th least significant bit is 1, then choose the i-th integer  
                if (x & (1 << i))  
                    sln.push_back(S[i]);  
            result.push_back(sln);  
        }  
        return result;  
    }  
};

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2016-09-23 ，如有侵权请联系 cloudcommunity@tencent.com 删除

dfs