Subsets
Given a set of distinct integers, return all possible subsets.
If S = [1,2,3], a solution is:
[ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]
Discussion
别整那么多，排列组合subset这一类的问题就是backtracing，确定两个问题就行了，1. 什么时候输出结果？2. 怎么在每一维上枚举各个candidate。回到这个问题上来，每一维i上对应的num[i]有可能被选中，也有可能不被选中，该再是各个number本身，而是出现还是不出现两种情况，例如三个不同数的subset是$$2^3$$这么多。
那什么时候输出呢？还是trace到第n维的时候，只是输出是对应的维度上出现number的情况。
Solution -- backtracing
class Solution {
public:
/**
* @param S: A set of numbers.
* @return: A list of lists. All valid subsets.
*/
vector<vector<int> > subsets(vector<int> &nums) {
// write your code here
vector<vector<int> > result;
if(nums.empty()) return result;
vector<bool> selected(nums.size(), false);
backtracing(nums, 0, result, selected);
return result;
}
private:
void backtracing(vector<int> &nums, int dim, vector<vector<int> > &records,
vector<bool> &selected) {
int n = nums.size();
if(dim == n) {
vector<int> solution;
for(int i=0; i<n; i++) {
if(selected[i] == true)
solution.push_back(nums[i]);
}
records.push_back(solution);
return;
}
selected[dim] = true;
backtracing(nums, dim+1, records, selected);
selected[dim] = false;
backtracing(nums, dim+1, records, selected);
}
};
上述方法输出条件直观，但是每个维度上枚举的是true or false，不太好想，另外当nums有重复数字的时候不好扩展（好吧也许可以扩展不过我实在想不出）。
另一个方案，修改Permutation的思路（这个题实在要好好理解了），首先是输出，不用等trace到dimension为N的时候输出，dimension为任意值的时候都可以输出（因为是subset）；其次还是每个维度枚举各个candidate，跟Permutation不同的是，在维度i上只能出现nums[i]或者之后的candidate，比如0 1 2 input, dim=1时，第1维只能为1或者2，subset为0 1, 0 2, 1 2. 对于1 2 这个case来说，第0维是1，那下一维只能是2了。如果第0维是2，那第一维就要至少是3，3不存在。 也就是说在枚举某个维度的时候，它的起始位置也要给出来。
class Solution {
public:
/**
* @param S: A set of numbers.
* @return: A list of lists. All valid subsets.
*/
vector<vector<int> > subsets(vector<int> &nums) {
// write your code here
vector<vector<int> > result;
if(nums.size() == 0) return result;
vector<int> solution(nums.size(), 0);
backtracing(nums, 0, 0, solution, result);
return result;
}
private:
void backtracing(vector<int> &nums, int dim, int start,
vector<int> &solution, vector<vector<int> > &records) {
vector<int> subset;
for(int i=0; i<dim; i++) {//m每次都输出，长度就是当前维度
subset.push_back(solution[i]);
}
records.push_back(subset);
for(int i = start; i<nums.size(); i++) {//不再是从0开始
solution[dim] = nums[i];
backtracing(nums, dim+1, i+1, solution, records);//枚举下一维度的时候起始位置是i+1
}
}
};
Solution --- DFS
A DFS solution. 这个是最基本的写法，也是个模板。
对原有数组排序，时间复杂度近似为 $$O(n \log n)$$. 状态数为所有可能的组合数 $$O(2^n)$$, 生成每个状态所需的时间复杂度近似为 O(1), 如[1] -> [1, 2], 故总的时间复杂度近似为 O(2^n)
使用了临时空间path 保存中间结果，path 最大长度为数组长度，故空间复杂度近似为 O(n).
class Solution {
public:
/**
* @param S: A set of numbers.
* @return: A list of lists. All valid subsets.
*/
vector<vector<int> > subsets(vector<int> &nums) {
// write your code here
vector<vector<int> > result;
int n = nums.size();
if(n==0) return result;
sort(nums.begin(), nums.end());
vector<int> solution;
dfs(nums, result, solution, 0);
return result;
}
private:
void dfs(vector<int> nums, vector<vector<int> > &result, vector<int> solution,
int pos) {
int n = nums.size();
result.push_back(solution);
for(int i=pos; i<n; i++) {
solution.push_back(nums[i]);
dfs(nums, result, solution, i+1);
solution.pop_back();
}
}
};
Solution --- Iteration
Iteration的思路。递增向量法。
用tmp记录上一轮结束后，所有子集；
考虑tmp中所有元素，加上nums[i]元素后多出来的集合，补充到result中
这里注意，利用一个中间变量tmp来保存ret上一轮的结果（或者保存上一组的指针）。
仔细想想，这套代码的思路与最开始递归代码的思路正好是逆向的：
**1）递归的代码是留出来当前元素，去寻找其余所有元素组成的子集集合
2）迭代的代码是每次添加当前元素，并更新所有子集集合，直到添加入最后一个元素**
class Solution {
public:
/**
* @param S: A set of numbers.
* @return: A list of lists. All valid subsets.
*/
vector<vector<int> > subsets(vector<int> &nums) {
// write your code here
vector<vector<int> > result;
int n = nums.size();
if(n==0) return result;
vector<int> none;
result.push_back(none);
for(int i=0; i<n; i++) {
vector<vector<int> > tmp = result;
result.reserve(tmp.size() * 2);
for(int j=0; j<tmp.size(); j++) {//当前结果里面每个子集都添加当前新元素nums[i]
tmp[j].push_back(nums[i]);
result.push_back(tmp[j]);
}
}
return result;
}
};
上面的代码每次还要用tmp记录所有的当前结果，这个构造既费时间又费空间，用一个previous size记录一下当前的结果就好了，然后扩展。
vector<vector<int> > subsets(vector<int> &nums) {
vector<vector<int> > result(1);
for(int i=0; i<nums.size(); i++) {
int size = result.size();
for(int j=0; j<size; j++) {
result.emplace_back(result[j]);
result.back().emplace_back(nums[i]);
}
}
return result;
}
Solution -- bit operation
Itereation. 基于位向量的算法。本方法的前提是：集合的元素不超过int 位数。用一个int 整数表示位向量，第i 位为1，则表示 选择S[i]，为0 则不选择。例如S={A,B,C,D}，则0110=6 表示子集{B,C}。
//// Time: O(n * 2^n)
// Space: O(1)
class Solution {
public:
/**
* @param S: A set of numbers.
* @return: A list of lists. All valid subsets.
*/
//use a n-bit vector to indicate which element is seleted, e.g.:
// 0110 --> nums[1], nums[2] are seleted in the current subset
vector<vector<int> > subsets(vector<int> &nums) {
vector<vector<int> > result;
if(nums.empty()) return result;
vector<int> path;
int total_num = 1 << nums.size(); // 2^n subsets in total
//this method words only if nums.size() is less than INT_MAX
for(size_t i=0; i < total_num; i++) {
for(int j=0; j<nums.size(); j++) {
if(i & (1<<j)) {// the j-th bit is 1
path.push_back(nums[j]);
}
}
result.push_back(path);
path.clear();
}
return result;
}
//0, 1, 2, 4, .... 2^n ==
};