题目链接：集合的子集
题目描述 请编写一个方法，返回某集合的所有非空子集。
给定一个int数组A和数组的大小int n，请返回A的所有非空子集。保证A的元素个数小于等于20，且元素互异。各子集内部从大到小排序,子集之间字典逆序排序，见样例。
测试样例：
[123,456,789]
返回：{[789,456,123],[789,456],[789,123],[789],[456 123],[456],[123]}
分析：这题可以采用两种方法，一种是递归求解，另一种是位输出法。分别如下：
class Subset {//递归的方法
public:
vector > getSubsets(vector A, int n)
{
Curse(A, n-1);
return res;
}
void Curse(vector A, int end)
{
if(end < 0)
{
if(temp.size() > 0)
res.push_back(temp);
return;
}
temp.push_back(A[end]);
Curse(A, end-1);
temp.pop_back();
Curse(A, end-1);
}private:
vector > res;
vector temp;
};
非递归的方法1： 时间复杂度很显然，最少也是2^n，空间复杂度，是n，每个元素要么在子集中，要么不在，用 j 的二进制形式的每一位代表数组a中对应的位置的元素是否在子集中，例如，当i = 5时， j = i = 5，那么j = 0101; 我们对应的输出 a[0], a[2]， 这个过程在while循环中完成。代码如下：
class Subset {
public:
vector > getSubsets(vector A, int n) {
vector > vv;
sort(A.begin(),A.end());
int i, j, k;
int t = 1 << n;
for (i = 0;
i < t;
i++)
{
j = i;
k = 0;
vector v;
while (j)
{
if (j & 1)
{
v.push_back(A[k]);
}
j >>= 1;
++k;
}
sort(v.begin(),v.end());
reverse(v.begin(),v.end());
if(v.size()!=0)
vv.push_back(v);
}
reverse(vv.begin(),vv.end());
return vv;
}
};
非递归的方法2：
class Subset {
public:
vector > getSubsets(vector A, int n) {
vector > result;
result.push_back(vector(1, A.back()));
for(int i = n-2;
i >= 0;
--i)
{
int size = result.size();
for(int j = 0;
j < size;
++j)
{
result.push_back(result[j]);
result[j].push_back(A[i]);
}
sort(result.begin(), result.end(), greater>());
result.push_back(vector(1, A[i]));
}
return result;
}
};
更多解法见 这里。
参考资料： 输出一个集合的所有子集（算法）
【算法与数据结构|集合的子集】
