Leetcode 78 - Subsets（枚举）

2019-11-08 03:15:10

字体：大中小

来源：转载

供稿：网友

题意

求一个set的所有子集

思路

算法1

二进制枚举

算法2

回溯法。

代码

//algorithm 1class Solution {public: vector<vector<int>> subsets(vector<int>& nums) { int n = nums.size(); vector<vector<int>> ans; for (int s = 0; s < (1 << n); s++) { vector<int> v; for (int i = 0; i < n; i++) { if (s & (1 << i)) v.push_back(nums[i]); } ans.push_back(v); } return ans; }};//algorothm 2class Solution {public: vector<int> a; vector<vector<int>> ans; void dfs(int pos, vector<int>& v) { if (pos == a.size()) { ans.push_back(v); return; } v.push_back(a[pos]); dfs(pos + 1, v); v.pop_back(); dfs(pos + 1, v); } vector<vector<int>> subsets(vector<int>& nums) { a = nums; vector<int> v; dfs(0, v); return ans; }};

上一篇：抽象类可以继承实体类吗？

下一篇：学习cifar(1)