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()是获取最后一个元素的迭代器，你可以理解为最后一个元素的指针.

接下来是第３种方法，Bit Manipulation　但还没学，再补充．

TODO Bit Manipulation

相关文章