Subsets

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

Note:

• Elements in a subset must be in non-descending order.

• 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],
  []
]

解题思路：

题意为找出一个集合的所有子集。题目要求结果中所有子集的元素升序排列，所以先将原来集合排序。然后通过递归回溯的方法枚举出所有子集。注意边界条件的判断。这里当下标大于数组的大小，就返回。每次我都会错一下。LeetCode运行时间4ms

class Solution {
public:
    vector> subsets(vector& nums) {
        std::sort(nums.begin(), nums.end());
        vector> result;
        vector item;
        subsetsHelper(result, nums, item, 0);
        return result;
    }
    
    void subsetsHelper(vector>& result, vector& nums, vector& item, int index){
        if(index>nums.size()){
            return;
        }
        result.push_back(item);
        for(int i=index; i
另外一种解法，可以用一个二进制来表示取哪些数。我们知道，一个n大小的集合的子集个数为2^n。从0枚举到2^n-1。然后通过位运算来检查哪些位为1即可。时间复杂度比上述方法大些。
class Solution {
public:
    vector> subsets(vector& nums) {
        std::sort(nums.begin(), nums.end());
        vector> result;
        
        int len = nums.size();
        double subsetNum = pow(2, len);
        
        for(int i=0; i item;
            
            int j=0;
            int k=i;
            while(k!=0){
                if(k&1){
                    item.push_back(nums[j]);
                }
                k = k>>1;
                j++;
            }
            
            result.push_back(item);
        }
        
        return result;
    }
};

 
转载请注明： » [LeetCode] Subsets

<!--
                    

                    	

                        	

                            	
                            
                        
                        

                        	

                            	
相关博文：
                                

                                	
                                    	
                                        	
                                        
                                        
定制桌面成功案例
                                    
                                    
                                    	
                                        	
                                        
                                        
海量文档查同或聚类问题 -- Locality Sensitive Hash 算法 （转）
                                    
                                    
                                    	
                                        	
                                        
                                        
汉字转拼音c/c++源码，支持gb2312和utf8
                                    
                                    
                                    	
                                        	
                                        
                                        
数据库顶级会议——SIGMOD介绍
                                    
                                
                            
                        
                    
                    -->