【LeetCode】78. Subsets (2 solutions)
LeetCode Solutions 78
2023-09-11 14:20:27 时间
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], [] ]
解法一:
遍历S.size()位数的所有二进制数,1代表对应位置的元素在集合中,0代表不在。
一共2^n种情况。
详细步骤参照Subsets II
class Solution { public: vector<vector<int> > subsets(vector<int> &S) { vector<vector<int> > result; int size = S.size(); for(int i = 0; i < pow(2.0, size); i ++) {//2^size subsets vector<int> cur; int tag = i; for(int j = size-1; j >= 0; j --) {//for each subset, the binary presentation has size digits if(tag%2 == 1) cur.push_back(S[j]); tag >>= 1; if(!tag) break; } sort(cur.begin(), cur.end()); result.push_back(cur); } return result; } };
解法二:
遍历所有元素,记当前元素为S[i]
遍历当前所有获得的子集,记为ret[j]
将S[i]加入ret[j],即构成了一个新子集。
详细步骤参照Subsets II
class Solution { public: vector<vector<int> > subsets(vector<int> &S) { sort(S.begin(), S.end()); vector<vector<int> > ret; vector<int> empty; ret.push_back(empty); for(int i = 0; i < S.size(); i ++) { int size = ret.size(); for(int j = 0; j < size; j ++) { vector<int> newset = ret[j]; newset.push_back(S[i]); ret.push_back(newset); } } return ret; } };
相关文章
- Java实现 LeetCode 786 第 K 个最小的素数分数(大小堆)
- Java实现 LeetCode 690 员工的重要性(简易递归)
- Java实现 LeetCode 1162 地图分析(可以暴力或者动态规划的BFS)
- Java实现 LeetCode 421 数组中两个数的最大异或值
- Java实现 LeetCode 29 两数相除
- LeetCode(115):不同的子序列
- LeetCode-901. 股票价格跨度【单调栈,巧妙】
- LeetCode-878. 第 N 个神奇数字【数学,二分查找,找规律】
- 【LeetCode 14】最长公共前缀
- Leetcode 2047. 句子中的有效单词数(可以,已解决)
- Leetcode 1395. 统计作战单位数(未完成)
- Leetcode Plus One
- leetcode 122. Best Time to Buy and Sell Stock II
- 【Mac系统】Vscode使用LeetCode插件报错‘leetcode.toggleLeetCodeCn‘ not found
- 【Leetcode刷题Python】343. 整数拆分
- 【13】罗马数字转整数【LeetCode】