Leetcode(78)-subsets

Given a set of distinct integers, S, 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 S = [1,2,3], a solution is:

[

[3],

[1],

[2],

[1,2,3],

[1,3],

[2,3],

[1,2],

[]

]

非递归解法：

思路：

拿给的例子[1,2,3]来说，最开始是空集，那么我们现在要处理1，就在空集上加1，为[1]，现在我们有两个子集[]和[1]，接下来在之前的子集基础上，每个都加个2，可以分别得到[2]，[1, 2]，那么现在所有的子集合为[], [1], [2], [1, 2]，同理处理3的情况可得[3], [1, 3], [2, 3], [1, 2, 3], 再加上之前的子集就是所有的子集合了，代码如下：

#include <iostream>
#include <vector>
using namespace std;

vector<int> input;
vector<vector<int>> ans;
vector<vector<int> > subsets(vector<int> &S) {
    vector<vector<int>> res();//初始化为1个元素，空
    sort(S.begin(),S.end());//要求非递减
    for(int i=;i<S.size();i++){
        int size=res.size();
        for(int j=;j<size;j++){
            res.push_back(res[j]);//加入上一轮已有的元素
            res.back().push_back(S[i]);//新加入一个元素
        }
    }
    return res;

}
int main(){
    int n,x;
    cin>>n;
    for(int i=;i<n;i++){
        cin>>x;
        input.push_back(x);
    }
    ans=subsets(input);
    for(int i=;i<ans.size();i++){
        cout<<"[";
        for(int j=;j<ans[i].size();j++){
            cout<<ans[i][j];
        }
        cout<<"]"<<endl;
    }
}
           

input:

3

1 2 3

output:

[]

[1]

[2]

[12]

[3]

[13]

[23]

[123]

递归解法,类似于dfs：

思路：

由于原集合每一个数字只有两种状态，要么存在，要么不存在，那么在构造子集时就有选择和不选择两种情况，所以可以构造一棵二叉树，左子树表示选择该层处理的节点，右子树表示不选择，最终的叶节点就是所有子集合，树的结构如下：

[]        
                   /          \        
                  /            \     
                 /              \
              [1]                []
           /       \           /    \
          /         \         /      \        
       [1 2]       [1]       [2]     []
      /     \     /   \     /   \    / \
  [1 2 3] [1 2] [1 3] [1] [2 3] [2] [3] []
           

vector<vector<int> > res;
vector<int> temp;
void getSubsets(vector<int> &S, int pos, vector<int> &temp, vector<vector<int> > &res) {
    res.push_back(temp);
    for (int i = pos; i < S.size(); ++i) {
        temp.push_back(S[i]);
        getSubsets(S, i + , temp, res);
        temp.pop_back();//删除最后一个元素pop_back()
    }
}
vector<vector<int> > subsets(vector<int> &S) {

    sort(S.begin(), S.end());
    getSubsets(S, , temp, res);
    return res;
}
           

牛客网上的这道题，要求按照元素个数非递减排序输出

void getSubsets(vector<int> &S, int pos,int k) {
    if(k<) return;
    else if(k==)
    {
        res.push_back(temp);

    }
    else{
        for (int i = pos; i < S.size(); ++i) {
        temp.push_back(S[i]);
        getSubsets(S, i + ,k-);
        temp.pop_back();//删除最后一个元素pop_back()
    }
    }
}
vector<vector<int> > subsets(vector<int> &S) {

    sort(S.begin(), S.end());
    for(int i=;i<=S.size();i++){
        getSubsets(S, , i);}//用i控制元素个数，保证有序
    return res;
}