Leetcode 78 Subsets

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:

代码语言：javascript复制

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

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

先贴上我的迭代深搜

代码语言：javascript复制

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次。

代码语言：javascript复制

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;  
    }  
};  

dfs distinct return set 集合

0 人点赞