// Source : https://oj.leetcode.com/problems/subsets/
// Author : Hao Chen
// Date : 2014-07-03
/**********************************************************************************
*
* 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],
* []
* ]
*
*
**********************************************************************************/
#include
#include
#include
#include
#include
#include
using namespace std;
void getCombination(vector& v, int n, int k, vector& solution, vector< vector >& result );
vector > combine(vector& v, int k);
vector > combine1(vector& v, int k);
vector > combine2(vector& v, int k);
vector > subsets(vector &S) {
vector > result;
for(int i=0; i<=S.size(); i++){
vector > r = combine(S, i);
result.insert(result.end(), r.begin(), r.end());
}
return result;
}
vector > combine(vector& v, int k) {
if (random()%2){
cout << "recusive method!" << endl;
return combine1(v, k);
}
cout << "non-recusive method!" << endl;
return combine2(v, k);
}
vector > combine1(vector &v, int k) {
vector > result;
vector solution;
getCombination(v, v.size(), k, solution, result);
return result;
}
void getCombination(vector &v, int n, int k, vector& solution, vector< vector >& result ){
if (k==0){
//sort to meet LeetCode requirement
vector v = solution;
sort(v.begin(), v.end());
result.push_back(v);
return;
}
for(int i=n; i>0; i--){
solution.push_back(v[i-1]);
getCombination(v, i-1, k-1, solution, result);
solution.pop_back();
}
}
vector > combine2(vector &v, int k) {
vector > result;
vector d;
int n = v.size();
for (int i=0; i tmp;
for(int x=0; x 0 ) ? 1 : 0;
ones--;
}
break;
}
if (d[i]==1) ones++;
}
if (!found){
break;
}
}
return result;
}
void printResult(vector >& result)
{
for(int i=0; i& v){
cout << "{";
for(int i=0; i1){
n = atoi(argv[1]);
}
vector v;
for(int i=n; i>0; i--){
v.push_back(i);
}
printArray(v);
vector > r = subsets(v);
printResult(r);
}