Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.
For example,
If n = 4 and k = 2, a solution is:
[ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]--------------------------------------------------------
combination, note that in this case, [1,2] and [2,1] are considered the same
we can use a stack instead of vector for vector<int> num
class Solution {
public:
void comb (vector<vector<int> >&ret, vector<int> num, vector<int> cur, int k) {
if (k == 0) {
ret.push_back(cur);
}else {
int size = num.size();
for (int i=0;i<size;i++) {
vector<int> temp = cur;
temp.push_back(num[0]);
num.erase(num.begin());
comb(ret,num,temp,k-1);
}
}
}
vector<vector<int> > combine(int n, int k) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector<int> num(n);
for (int i=0;i<n;i++) {
num[i] = 1+i;
}
vector<int> cur;
vector<vector<int> > ret;
comb(ret,num,cur,k);
return ret;
}
};
Update on Sep-16-2014 class Solution {
public:
void comb (vector<vector<int> > &rt, vector<int> cur, int n, int k, int index) {
if (k == 0) {
rt.push_back(cur);
return;
}
for (int i = index; i <= n + 1 - k; i++) {
vector<int> temp = cur;
temp.push_back(i);
comb(rt,temp,n,k - 1,i + 1);
}
}
vector<vector<int> > combine(int n, int k) {
vector<vector<int> > rt;
vector<int> v;
comb(rt,v,n,k,1);
return rt;
}
};
同subsets的bit operation的方法
class Solution {
public:
void helper(vector<vector<int>> &rt,vector<int> cur, int n, int k, int index) {
if (k == 0) {
rt.push_back(cur);
return;
}
if (k < 0 || index > n) return;
helper(rt,cur,n,k,index + 1);
cur.push_back(index);
helper(rt,cur,n,k - 1,index + 1);
}
vector<vector<int>> combine(int n, int k) {
vector<vector<int> > rt;
vector<int> cur;
helper(rt,cur,n,k,1);
return rt;
}
};
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.
If S =
[1,2,3], a solution is:[ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]--------------------------------------------------
Solution #1 recursive, Combination
class Solution {
public:
void sub (vector<vector<int> > &ret, vector<int> S, vector<int> cur) {
if (S.size() != 0) {
int size = S.size();
for (int i=0;i<size;i++) {
vector<int> temp = cur;
temp.push_back(S[0]);
S.erase(S.begin());
ret.push_back(temp);
sub(ret,S,temp);
}
}
}
vector<vector<int> > subsets(vector<int> &S) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
sort(S.begin(),S.end());
vector<vector<int> > ret;
vector<int> cur;
ret.push_back(cur);
sub(ret,S,cur);
return ret;
}
};
Update on Sep-17-2014 class Solution {
public:
void sub(vector<vector<int> > &rt, vector<int> cur, vector<int> S, int index) {
rt.push_back(cur);
for (int i = index; i < S.size(); i++) {
vector<int> temp = cur;
temp.push_back(S[i]);
sub(rt,temp,S,i + 1);
}
}
vector<vector<int> > subsets(vector<int> &S) {
sort(S.begin(),S.end());
vector<vector<int> > rt;
vector<int> v;
sub(rt,v,S,0);
return rt;
}
};
Update on Nov-01-2014 Solution #2, Bitmap
For each S it has 2^S.size() subsets and each for loop iteration generates one subset
1 2 3
------
0 0 0
0 0 1
0 1 0
0 1 1
...
class Solution {
public:
vector<vector<int> > subsets(vector<int> &S) {
int numOfSubsets = 1 << S.size();
sort(S.begin(),S.end());
vector<vector<int> > rt;
for (int i = 0; i < numOfSubsets; i++) {
int pos = 0;
int bitMask = i;
vector<int> sub;
while (bitMask > 0) {
if ((bitMask & 1) == 1) {
sub.push_back(S[pos]);
}
bitMask >>= 1;
pos++;
}
rt.push_back(sub);
}
return rt;
}
};
Update on Nov-18-2014
Solution #3 iterative
class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int> > rt;
vector<int> cur;
rt.push_back(cur);
sort(nums.begin(),nums.end());
for (int i = 0; i < nums.size(); i++) {
vector<vector<int> > temp = rt;
for (int j = 0; j < temp.size(); j++) {
temp[j].push_back(nums[i]);
rt.push_back(temp[j]);
}
}
return rt;
}
};
Update on July-5th-2015
每个数字都可以为 “有” 或 “无”
class Solution {
public:
void helper(vector<vector<int> > &rt, vector<int> nums, vector<int> cur,int index) {
if (index == nums.size()) {
rt.push_back(cur);
return;
}
helper(rt,nums,cur,index + 1);
cur.push_back(nums[index]);
helper(rt,nums,cur,index + 1);
}
vector<vector<int>> subsets(vector<int>& nums) {
sort(nums.begin(),nums.end());
vector<vector<int> > rt;
vector<int> cur;
helper(rt,nums,cur,0);
return rt;
}
};
ToDo, 以上所有解法要再看一次
