Leetcode 78 Subsets + 90 Subsets II 子集

本文主要是介绍Leetcode 78 Subsets + 90 Subsets II 子集，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

原题地址：https://leetcode.com/problems/subsets/

题目描述

Given a set of distinct integers, nums, return all possible subsets.
给出一个不包含重复元素的整形数组，返回所有可能的子集。
Note:
注意：
Elements in a subset must be in non-descending order.
子集中的元素要以非递减顺序排序。
The solution set must not contain duplicate subsets.
结果集中不能有重复的子集。

解题思路

这个题可以用动态规划来解，我们每次只需考虑对于某个元素，是否要把它放入到子集中，要么放进去要么不放进去，这样得到的是两个不同的子集。

可以用递归调用，获取其后所有元素的子集，然后遍历子集，把每一个子集添加到结果集中，并并把每一个子集添加当前元素之后再把它添加到当前结果集中。

算法描述

将数组排序
对于第i个元素，获取其之后元素（i+1之后的所有元素）的所有子集，然后遍历其所有子集（i+1之后），将每一个子集添加到当前的结果集中，并把每一个子集添加第i个元素之后再把它添加到当前结果集中。

代码

class Solution {
public:vector<vector<int> > subsets(vector<int>& nums) {// 原始数据排序sort(nums.begin(), nums.end());// 返回第0个元素之后的所有元素组成的集合的子集return subsets(nums, 0, nums.size());}// 返回nums数组中第cur个元素及其之后所有元素组成的集合的所有的子集// nums: 原始数据// cur: 当前处理的元素// len: 原始数据长度vector<vector<int> > subsets(vector<int>& nums, int cur, int len) {// 如果当前元素已经超出数据边界，返回一个空集（空集是任意集合的子集）if (cur == len) {vector<vector<int> > ret;vector<int> tmp;ret.push_back(tmp);return ret;}// 获取第cur个元素之后的所有元素组成的集合的所有子集vector<vector<int> > ret = subsets(nums, cur + 1, len);// 先将这些子集添加到结果集中vector<vector<int> > retTmp;copy(ret.begin(), ret.end(), back_inserter(retTmp));// 把每个子集的首位置添加当前元素，然后加入到结果集中for (int i = 0; i < ret.size(); ++i) {vector<int> tmp = ret[i];tmp.insert(tmp.begin(), nums[cur]);retTmp.push_back(tmp);}return retTmp;}
};

运行情况

Status : Accepted
Run Time : 10ms

一点延伸 Leetcode 90 Subsets II

2015/5/14更新

额，今天发现之前考虑过的这种情况就是Leetcode 90的题目内容。下面的代码稍作改动（其实就只是改了个函数名），提交到oj上Accept，不过运行时间不是很好，28ms，看别人大部分分布在16ms左右。暂时先这样吧。

题目中说了，不允许出现重复的子集。由于原始数据中不存在重复的元素，因此子集不重复还是很好做的，那么问题来了，如果原始数据中有重复数据怎么办呢？例如 [1, 1, 2, 3] 用上述程序跑出来结果是：

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

显然有很多重复的子集。

一个很自然而然的解决思路是，按照上述算法求出子集，然后去除重复的子集即可。

为了方便的去除重复的子集，将所有子集先排序再处理比较容易。

代码如下：

class Solution {
public:vector<vector<int> > subsetsWithDup(vector<int>& nums) {// 原始数据排序sort(nums.begin(), nums.end());// 返回第0个元素之后的所有元素组成的集合的子集vector<vector<int> > ret = subsets(nums, 0, nums.size());// 子集排序sort(ret.begin(), ret.end());// 去重vector<vector<int> >::iterator pre = ret.begin(), cur = pre + 1, last = ret.end();vector<vector<int> > retTmp;retTmp.push_back(ret[0]);while (cur != last) {if ((*pre).size() != (*cur).size()) { // 如果当前子集与前一个非重子集长度不同，则肯定为不同的子集retTmp.push_back(*cur); // 添加当前子集pre = cur; // 更新前一个非重子集++cur; // 指针后移} else { // 如果当前子集与前一个非重子集长度相同，则挨个判断，看是否相同bool same = true;int len = (*pre).size();for (int i = 0; i < len; ++i) {if ((*pre)[i] != (*cur)[i]) { // 如果某个位置元素不同，则两子集不相同same = false;break;}}if (!same) { // 如果当前子集与前一个非重子集不同retTmp.push_back(*cur); // 添加当前子集pre = cur; // 更新前一个非重子集}++cur; // 指针后移}}return retTmp;}vector<vector<int> > subsets(vector<int>& nums, int cur, int len) {// 如果当前元素已经超出数据边界，返回一个空集（空集是任意集合的子集）if (cur == len) {vector<vector<int> > ret;vector<int> tmp;ret.push_back(tmp);return ret;}// 获取第cur个元素之后的所有元素组成的集合的所有子集vector<vector<int> > ret = subsets(nums, cur + 1, len);// 先将这些子集添加到结果集中vector<vector<int> > retTmp;copy(ret.begin(), ret.end(), back_inserter(retTmp));// 把每个子集的首位置添加当前元素，然后加入到结果集中for (int i = 0; i < ret.size(); ++i) {vector<int> tmp = ret[i];tmp.insert(tmp.begin(), nums[cur]);retTmp.push_back(tmp);}return retTmp;}
};