求集合S的所有子集

---

---

刷题平台

牛客网

题目描述

现在有一个没有重复元素的整数集合S，求S的所有子集

注意：

• 你给出的子集中的元素必须按不下降的顺序排列
• 给出的解集中不能出现重复的元素

例如：

如果S=[1,2,3], 给出的解集应为：

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

解题思路

想到求一个数组的子集，一定会想到按照每个子集中元素的个数分为几大类，然后再找出每类符合条件的所有子集。如题中给的例子：S=[1, 2, 3]

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

所以需要构造一个子函数，实现只有一个元素的所有子类；只有两个元素的所有子类；…

具体构造过程参考代码：

代码

class Solution
{
public:
    vector<vector<int> > subsets(vector<int> &S)
    {
        // 首先对给出输入进行排序，因为题目要求子集合按照不下降的顺序排列
        sort(S.begin(), S.end()); 
        
        // 然后找到含有不同元素的各自子集合
        for (int i = 0; i <= S.size(); i++) // 包含S.size()
            Sort(S, 0, i);
        
        return result;
    }
private:
    vector<int> tmp; // 存放临时子集合
    vector<vector<int> > result;
    // start: S数组中开始遍历的首元素； num:子集合含有元素的个数
    void Sort(vector<int> &S, int start, int num)
    {
        if (num < 0) //递归终止条件
            return ;
        else if (num == 0)
            result.push_back(tmp);
        else
        {
            for (int j = start; j < S.size(); j++)
            {
                tmp.push_back(S[j]);
                Sort(S, j+1, num-1);
                tmp.pop_back();
            }
        }
    }
};