所有子集 剑指 Offer II 079

我只是喜欢敲代码@_@

目录

题目描述

AC代码

思路分析

---

题目描述

给定一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例 1：

输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2：

输入：nums = [0]
输出：[[],[0]]

提示：

1 <= nums.length <= 10
-10 <= nums[i] <= 10
nums 中的所有元素 互不相同

AC代码

class Solution {
public:
    vectorint>> subsets(vector<int>& nums) {
    	setint>>sons;
    	for(auto & num:nums){
    		setint>>temp;
			for(auto it:sons){
				it.push_back(num);
				temp.insert(it);
			}
			sons.insert(temp.begin(),temp.end());
			sons.insert({num}); 		
		}
		vectorint>>answer;
		answer.push_back({});
		for(auto & it:sons)
		answer.push_back(it);
		return answer;
    }
};

思路分析

先说一下解法哈，子集问题有很多种解决方法，我写的这个只有两层循环，回溯递归之类的也能写，这是C++写的代码，有大佬可以用四行python解决，同样的解决思路。

 

对于一串数字，我们想要找出它的所有子集，像1，2，3这个，我们第一次取出1，它自己本身是一个子集，我们把它存起来，第二次取出2，把2插入之前找到的子集中，就有了1，2这个子集，再把它自己存进去，第三次取出3，把3插入之前找到的子集，这样就会有1，3和2，3和1，2，3这些子集，再把3自己存进去。

基本思路是这样，实际操作的时候，会出现重复的子集，所以我们需要先用set来去重，嘻嘻嘻，你会不会有一个疑惑，为什么不一开始就用set，非要我们返回一个vector的呢，我起初也有这样的疑惑，直到我发现set不会存在{}这个空集，而vector可以装一个{}的时候就豁然开朗了。

 

还有一个问题，我依照这样的思路写的第一次代码其实长这样：

    	for(auto num:nums){
			for(auto it:sons){
				it.push_back(num);
				sons.insert(it);
			}
			sons.insert({num}); 		
		}

没有引入一个临时变量temp，直到运行超时，手动调试发现这个地方无限循环，原因在于sons每次都加一个元素，然后就不会终结循环，所以得引入一个变量。