78. Subsets(中等,集合的子集,经典问题 DFS)

时间:2021-06-07 04:01:54

Given a set of distinct integers, nums, return all possible subsets.

Note: The solution set must not contain duplicate subsets.

For example,

If nums = [1,2,3], a solution is:

[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]

就是求指定集合的所有子集.

三种解法:

  • Recursive (Backtracking) 道理能理解,代码不容易写;
  • Iterative 本文用的解法,好直接,易理解和实现
  • Bit Manipulation 还没学,再补充.

方法1, Recursive (Backtracking)

代码中的注释是我的理解.

// Recursive (Backtracking)
vector<vector<int>> subsets(vector<int>& A) {
sort(A.begin(), A.end()); // sort
vector < vector<int> > res;
vector<int> sub; // 四个参数
// A, 二维res, 临时sub, 待处理数组A元素索引号indx
genSubset(A, res, sub, 0);
return res;
} // DFS:
// box 套 box, 好奇的小儿一直往里面开 box
void genSubset(vector<int>& A, vector<vector<int> >& res, vector<int> sub,
int start) {
res.push_back(sub);
for (int i = start; i < A.size(); i++) {
// 假设 sub = [1]
// sub里压入一个2, sub = [1, 2]
sub.push_back(A[i]); // 看看压入2后, 还有谁?!!
genSubset(A, res, sub, i + 1); // 还有谁的事,由genSubset探查完后,
// 把2弹出去, sub = [1], 然后下轮循环, 看看谁还能和 1 搭个伴,
// 假设A中还有3, 那么下次循环 sub = [1, 3]
// 直到 1 和所有A中剩余元素都结合过
sub.pop_back();
}
}

方法2, Iterative

想法:

就是编程实现下面的东西:

[[]]
[[], []] --> [[], [1]]
[[],[1]] -复制-> [[],[1],[],[1]] -添值-> [[],[1],[2],[1, 2]]
[[],[1],[2],[1, 2]] -复制-> [[],[1],[2],[1, 2],[],[1],[2],[1, 2]] -添值-> [[],[1],[2],[1, 2],[3],[1,3],[2,3],[1, 2, 3]]

上面的例子不太准确(细节写准确太长了,下面针对一个小东西仔细描述过程),但思路是对的.

下面才是程序真正的执行结果:

应该是这样的,我们拿出一小段做解释^^
[[],[1]] -复制-> [[],[1],[]] -添值-> [[],[1],[2]] -复制-> [[],[1],[2],[1]] -添值-> [[],[1],[2],[1,2]]

人家想法,自己代码:

\(O(n^2)\) time, \(O(1)\) extra space.

vector<vector<int>> subsets(vector<int>& A) {
sort(A.begin(), A.end()); // sort
vector < vector<int> > res(1, vector<int>()); // declare res = [[],];
const int n = A.size(); for (int i = 0; i < n; i++) {
const int m = res.size();
for (int j = 0; j < m; j++) {
// 有坑, 注意, 不可妄图写成下面这样:
// res.push_back(res[j].push_back(A[i]));
res.push_back(res[j]); // [[], []]
res.back().push_back(A[i]); // [[], [1]]
}
}
return res;
}

顺便上面代码展示了一些关于c++写代码的副产品,如下:

  1. 声明一个 [[],] 的二维数组: vector < vector<int> > res(1, vector<int>());
  2. 这么写结果不对: for(auto it : res) res.push_back(it.push_back(A[i])); 我晕!
  3. 不能妄图写成这样: res.push_back(res[j].push_back(A[i])); 有点边迭代,边修改数组的意思.
  4. push_back() 和 back() 的区别:
    • coll.push_back()是把一个元素,放入这个容器的末尾,相当于末尾添加一个元素;
    • coll.back()是获取最后一个元素的迭代器,你可以理解为最后一个元素的指针.

接下来是第3种方法,Bit Manipulation 但还没学,再补充.

TODO Bit Manipulation