# 78. Subsets

## 描述

Given a set of distinct integers, nums, return all possible subsets.

Note: The solution set must not contain duplicate subsets.

For example, If nums = [1,2,3], a solution is:

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


## 分析

[
[ ]
]


[
[ ]
[1]
]


[
[ ]
[1]
[1 2]
[2]
]


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


………………

/*Solution1 ,Iteration*/
class Solution {
public:
vector<vector<int> > subsets(vector<int> &S) {
vector<vector<int>> res(1);
for(int i=0;i<S.size();++i){
int size=res.size();
for(int j=0;j<size;j++){
res.push_back(res[j]);
res.back().push_back(S[i]);
}
}
return res;
}
};


subsets([1 2 3 4])=[]
//push(1)
[1,subsets[2 3 4]]
//pop,push(2)
[2,subsets[3,4]]
//pop,push(3)
[3,subsets[4]]
//pop,push(4)
[4,subsets[]]
//pop


/*Solution2 Recursion*/
class Solution {
private:
void backtracking(vector<int> & nums,vector<int> & sub,vector<vector<int>> & subs,int start){
subs.push_back(sub);
for(int i=start;i<nums.size();++i){
sub.push_back(nums[i]);
backtracking(nums,sub,subs,i+1);
sub.pop_back();
}
}
public:
vector<vector<int> > subsets(vector<int> &S) {
vector<vector<int>> subs;
vector<int> sub;
backtracking(S,sub,subs,0);
return subs;
}
};


### 学籍管理系统文档

#### 北邮教务系统评教脚本

Published on September 17, 2017

#### 72.Edit distance

Published on September 17, 2017