首页 > 代码库 > Leetcode-subsets
Leetcode-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排序,然后再求全部的子集。
我的方法是笨方法,如求S= [1, 2, 3]的全部子集时:
1、首先对S排序,当然排完序还是S= [1, 2, 3];
2、计算元素个数为[S.size() - 1] = 2的全部子集,设为S2, 则S2 = {[1, 2], [1, 3], [2, 3]}
3、计算元素个数为[S2.size() - 1] = 1的全部子集,设为S1。则S1 = {[1], [2], [3]}
4、设空集为S0。 则全部的字串的字集为 {S、S2、S1、 S0}
这种方法能够使用递归实现。可是假设S的元素个数比較大的时候,使用递归会出"Time Limit Exceeded"的错误,所以不能使用递归实现。
以下是我的代码,我会继续思考好的方法。
#include "stdafx.h" #include <iostream> #include <vector> #include <set> #include <algorithm> using namespace std; void maxSubsets(const vector<int> &S, set<vector<int> > &tmpSet) { for (int i = 0; i < S.size(); i++) { vector<int> subset; for (int j = 0; j < S.size(); j++) { if (j != i) subset.push_back(S[j]); } tmpSet.insert(subset); } } vector<vector<int> > subsets(vector<int> &S) { sort(S.begin(), S.end()); set<vector<int> > vecSet; vector<vector<int> > allSubset; vecSet.insert(S); // 记录下全集 allSubset.push_back(S); //子集元素的个数从S.size()个到1个,每运行完一次循环,子集元素个数减1 for ( int i = 0; i < S.size() - 1; i++ ) { set<vector<int> > tmpSet; // 获取下一级的全部子集 for (set<vector<int> >::iterator iter = vecSet.begin(); iter != vecSet.end(); iter++) maxSubsets(*iter, tmpSet); // 记录子集 for (set<vector<int> >::iterator iter = tmpSet.begin(); iter != tmpSet.end(); iter++) allSubset.push_back(*iter); vecSet.clear(); vecSet.insert(tmpSet.begin(), tmpSet.end()); } // 记录空集 vector<int> empty; allSubset.push_back(empty); return allSubset; } int _tmain(int argc, _TCHAR* argv[]) { vector<int> data; data.push_back(1); data.push_back(2); data.push_back(3); data.push_back(4); vector<vector<int> > res = subsets(data); for (int i = 0; i < res.size(); i++) { vector<int> subset = res[i]; for (int j = 0; j < subset.size(); j++) cout << subset[j] << " "; cout << endl; } cout << "Size: " << res.size() << endl; return 0; }
Leetcode-subsets
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。