子集 - LintCode

103 阅读 0 评论 68 点赞

我是靠谱客的博主跳跃鱼，这篇文章主要介绍子集 - LintCode，现在分享给大家，希望可以做个参考。

描述
给定一个含不同整数的集合，返回其所有的子集
子集中的元素排列必须是非降序的，解集必须不包含重复的子集

样例
如果 S = [1,2,3]，有如下的解：

复制代码

1
2
3
4
5
6
7
8
9
10
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

挑战
你可以同时用递归与非递归的方式解决么？

思路
从右到左处理nums的元素，当res为空，将{}，{nums.back()}存入res，并删除nums的末尾元素。若res不为空，对于每个元素res[i]，加上nums.back()，再添加到res中，删除nums的末尾元素。直至nums为空。

复制代码

#ifndef C17_H
#define C17_H
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
bool cmp(const int a, const int b)
{
    return a > b;
}
class Solution {
public:
    /**
    * @param nums: A set of numbers
    * @return: A list of lists
    */
    vector<vector<int>> subsets(vector<int> &nums) {
        // write your code here
        if (nums.empty())
            return{ {} };
        //构建降序数组
        sort(nums.begin(), nums.end(), cmp);
        //从数组尾部开始添加数据
        //新的res是原res再加上每个res元素加上nums的尾部
        while (!nums.empty())
        {
            if (res.empty())
            {
                res.push_back({ nums.back() });
                res.push_back({});
            }
            else
            {
                int len = res.size();
                for (int i = 0; i < len; ++i)
                {
                    vector<int> temp = res[i];
                    temp.push_back(nums.back());
                    res.push_back(temp);
                }
            }
            nums.pop_back();
        }
        return res;
    }
    vector<vector<int>> res;
};
#endif

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#ifndef C17_H
#define C17_H
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
bool cmp(const int a, const int b)
{
    return a > b;
}
class Solution {
public:
    /**
    * @param nums: A set of numbers
    * @return: A list of lists
    */
    vector<vector<int>> subsets(vector<int> &nums) {
        // write your code here
        if (nums.empty())
            return{ {} };
        //构建降序数组
        sort(nums.begin(), nums.end(), cmp);
        //从数组尾部开始添加数据
        //新的res是原res再加上每个res元素加上nums的尾部
        while (!nums.empty())
        {
            if (res.empty())
            {
                res.push_back({ nums.back() });
                res.push_back({});
            }
            else
            {
                int len = res.size();
                for (int i = 0; i < len; ++i)
                {
                    vector<int> temp = res[i];
                    temp.push_back(nums.back());
                    res.push_back(temp);
                }
            }
            nums.pop_back();
        }
        return res;
    }
    vector<vector<int>> res;
};
#endif