程序员面试金典

程序员面试金典--集合的子集

 

题目描述

请编写一个方法，返回某集合的所有非空子集。

给定一个int数组A和数组的大小int n，请返回A的所有非空子集。保证A的元素个数小于等于20，且元素互异。各子集内部从大到小排序,子集之间字典逆序排序，见样例。

测试样例：

[123,456,789]

返回：{[789,456,123],[789,456],[789,123],[789],[456 123],[456],[123]}

 

看到牛客网的discuss上的， 使用二进制，二进制每次减去1， 则其二进制数的字典序降一。（ 二进制逐次减一，就得到一串字典序（从高到低的））

 

 

class Subset {
public:

    vector<vector<int> > getSubsets(vector<int> A, int n) {
        // write code here
        sort(A.begin(), A.end());  

        int num = 1 << n; 

        vector<vector<int> > ans; 

        for(int i= num - 1; i>0; --i) {
            vector<int> tmp; 

            for(int j=n-1; j>=0; --j) {
                if( (i >> j) & 1 ) {
                    tmp.push_back(A[j]); 
                }  
            }

            ans.push_back(tmp); 
        }

        return ans;  
    }
};