# 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],
[]
]
``````

``````class Solution {
public:
vector<vector<int> > subsets(vector<int> &S) {
vector<vector<int> > res(1);
sort(S.begin(), S.end());
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;
}
};
``````

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

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

``````class Solution {
public:
vector<vector<int> > subsets(vector<int> &S) {
vector<vector<int> > res;
vector<int> out;
sort(S.begin(), S.end());
getSubsets(S, 0, out, res);
return res;
}
void getSubsets(vector<int> &S, int pos, vector<int> &out, vector<vector<int> > &res) {
res.push_back(out);
for (int i = pos; i < S.size(); ++i) {
out.push_back(S[i]);
getSubsets(S, i + 1, out, res);
out.pop_back();
}
}
};
``````

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

1 2 3 Subset
0 F F F []
1 F F T 3
2 F T F 2
3 F T T 23
4 T F F 1
5 T F T 13
6 T T F 12
7 T T T 123

``````class Solution {
public:
vector<vector<int> > subsets(vector<int> &S) {
vector<vector<int> > res;
sort(S.begin(), S.end());
int max = 1 << S.size();
for (int k = 0; k < max; ++k) {
vector<int> out = convertIntToSet(S, k);
res.push_back(out);
}
return res;
}
vector<int> convertIntToSet(vector<int> &S, int k) {
vector<int> sub;
int idx = 0;
for (int i = k; i > 0; i >>= 1) {
if ((i & 1) == 1) {
sub.push_back(S[idx]);
}
++idx;
}
return sub;
}
};
``````

Github 同步地址：

https://github.com/grandyang/leetcode/issues/78

Subsets II

Generalized Abbreviation

Letter Case Permutation

https://leetcode.com/problems/subsets/

https://leetcode.com/problems/subsets/discuss/27288/My-solution-using-bit-manipulation

https://leetcode.com/problems/subsets/discuss/27278/C%2B%2B-RecursiveIterativeBit-Manipulation

https://leetcode.com/problems/subsets/discuss/27281/A-general-approach-to-backtracking-questions-in-Java-(Subsets-Permutations-Combination-Sum-Palindrome-Partitioning)

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation