首页 > 递归/回溯:Subsets II求子集(有重复元素)

递归/回溯:Subsets II求子集(有重复元素)

上一篇描述了针对数组中没有重复元素进行子集的求取过程递归/回溯:subsets求子集

但是当出现如下数组时:

例如: nums[] = [2, 1, 2, 2]

结果为: [[], [1], [1,2], [1,2,2], [1,2,2,2], [2], [2,2], [2,2,2]]

注意: [2,1,2]与[1,2,2]是重复的集合,则不满足集合的要求。

思考:

同样的递归回溯方式,即每一个元素在是否需要加入到集合中都会有两种状态,存在或者不存在,这里加入的过程中可以对子集进行筛选,如果之前的子集中已经存在有相同的集合,则不需要加入;否则,再将筛选出来的子集加入到最终的集合中。

实现过程如下:

方法一,递归回溯实现

void generate(int i, std::vector<int> &num,std::vector<int> &item,std::vector<std::vector<int>> &result,std::set<std::vector<int>> &uniq_result) { if (i >= num.size()) { return;}item.push_back(num[i]);/*当集合中没有当前item时,则加入最终的子集中*/if (uniq_result.find(item) == uniq_result.end()) {  result.push_back(item);uniq_result.insert(item);}generate(i + 1, num, item, result, uniq_result);item.pop_back();generate(i + 1, num, item, result, uniq_result);
}/*method1*/
std::vector<std::vector<int> > get_subsets(std::vector<int> &num) { std::vector<int> item;std::vector<std::vector<int>> result;std::set<std::vector<int> > uniq_result;//维护一个集合sort(num.begin(), num.end());//对初始序列进行排序result.push_back(item);generate(0, num, item, result, uniq_result);return result;
}

方法二,位运算实现

/*method2*/
std::vector<std::vector<int> > get_subsets2(std::vector<int> &num) { std::vector<std::vector<int>> result;std::set<std::vector<int> > uniq_result;int all_set = 1 << num.size();sort(num.begin(), num.end());for (int i = 0;i < all_set; ++i) { std::vector<int> item;for (int j = 0;j < num.size(); ++j) { if (i & (1 << j)) { item.push_back(num[j]);}}/*同样使用集合来判断是否需要加入最终的子集中*/if (uniq_result.find(item) == uniq_result.end()) { result.push_back(item);uniq_result.insert(item);}}return result;
}

测试代码如下:

测试[2,1,2,2]

#include 
#include 
#include 
#include /*
Subsets II已知一组数(其中有重复元素),求这组数可以组成的所有子集。 结果中无重复的子集。
例如: nums[] = [2, 1, 2, 2]
结果为: [[], [1], [1,2], [1,2,2], [1,2,2,2], [2], [2,2], [2,2,2]]
注意: [2,1,2]与[1,2,2]是重复的集合
*/using namespace std;void generate(int i, std::vector<int> &num,std::vector<int> &item,std::vector<std::vector<int>> &result,std::set<std::vector<int>> &uniq_result) { if (i >= num.size()) { return;}item.push_back(num[i]);if (uniq_result.find(item) == uniq_result.end()) { result.push_back(item);uniq_result.insert(item);}generate(i + 1, num, item, result, uniq_result);item.pop_back();generate(i + 1, num, item, result, uniq_result);
}/*method1*/
std::vector<std::vector<int> > get_subsets(std::vector<int> &num) { std::vector<int> item;std::vector<std::vector<int>> result;std::set<std::vector<int> > uniq_result;sort(num.begin(), num.end());result.push_back(item);generate(0, num, item, result, uniq_result);return result;
}/*method2*/
std::vector<std::vector<int> > get_subsets2(std::vector<int> &num) { std::vector<std::vector<int>> result;std::set<std::vector<int> > uniq_result;int all_set = 1 << num.size();sort(num.begin(), num.end());for (int i = 0;i < all_set; ++i) { std::vector<int> item;for (int j = 0;j < num.size(); ++j) { if (i & (1 << j)) { item.push_back(num[j]);}}if (uniq_result.find(item) == uniq_result.end()) { result.push_back(item);uniq_result.insert(item);}}return result;
}int main(int argc, char const *argv[])
{ std::vector<int> num;std::vector<int> item;std::vector<std::vector<int>> result;std::vector<std::vector<int>> result2;int tmp;int N;std::cin >> N;for (int i  = 0;i < N; ++i) { std::cin >> tmp;num.push_back(tmp);}result = get_subsets(num);result2= get_subsets2(num);cout << "method1 " << endl;for (int i = 0;i < result.size(); ++i) { if (result[i].size() == 0) { cout << "[]";}for (int j = 0;j < result[i].size(); ++j) { std::cout << "[" << result[i][j] << "] ";}std::cout << std::endl;}cout << "method2 " << endl;for (int i = 0;i < result2.size(); ++i) { if (result2[i].size() == 0) { cout << "[]";}for (int j = 0;j < result2[i].size(); ++j) { std::cout << "[" << result2[i][j] << "] ";}std::cout << std::endl;}	return 0;
}

输出如下:

4
2 1 2 2
method1 
[]
[1] 
[1] [2] 
[1] [2] [2] 
[1] [2] [2] [2] 
[2] 
[2] [2] 
[2] [2] [2] 
method2 
[]
[1] 
[2] 
[1] [2] 
[2] [2] 
[1] [2] [2] 
[2] [2] [2] 
[1] [2] [2] [2]

更多相关:

  • 经过长期探索,发现一个不需要手动设置线程休眠时间(e.g. std::this_thread::sleep_for(std::chrono::microseconds(1)))的代码: Github: https://github.com/log4cplus/ThreadPool #ifndef THREAD_POOL_H_7e...

  • nth_element(first,nth,last) first,last 第一个和最后一个迭代器,也可以直接用数组的位置。  nth,要定位的第nn 个元素,能对它进行随机访问. 将第n_thn_th 元素放到它该放的位置上,左边元素都小于它,右边元素都大于它. 测试代码: http://www.cplusplus.com...

  • c/c++老版本的rand()存在一定的问题,在转换rand随机数的范围,类型或者分布时,常常会引入非随机性。 定义在 中的随机数库通过一组协作类来解决这类问题:随机数引擎 和 随机数分布类 一个给定的随机数发生器一直会生成相同的随机数序列。一个函数如果定义了局部的随机数发生器,应该将(引擎和分布对象)定义为 st...

  • jsoncpp 是一个C++ 语言实现的json库,非常方便得支持C++得各种数据类型到json 以及 json到各种数据类型的转化。 一个json 类型的数据如下: {"code" : 10.01,"files" : "","msg" : "","uploadid" : "UP000000" } 这种数据类型方便我们人阅读以...

  • 问题如下: 已知一组数(其中有重复元素),求这组数可以组成的所有子集中,子 集中的各个元素和为整数target的子集,结果中无重复的子集。 例如: nums[] = [10, 1, 2, 7, 6, 1, 5], target = 8 结果为: [[1, 7], [1, 2, 5], [2, 6], [1, 1, 6]] 同样之前有...

  •         Apache POI是一个开源的利用Java读写Excel,WORD等微软OLE2组件文档的项目。        我的需求是对Excel的数据进行导入或将数据以Excel的形式导出。先上简单的测试代码:package com.xing.studyTest.poi;import java.io.FileInputSt...

  • 要取得[a,b)的随机整数,使用(rand() % (b-a))+ a; 要取得[a,b]的随机整数,使用(rand() % (b-a+1))+ a; 要取得(a,b]的随机整数,使用(rand() % (b-a))+ a + 1; 通用公式:a + rand() % n;其中的a是起始值,n是整数的范围。 要取得a到b之间的...

  • 利用本征图像分解(Intrinsic Image Decomposition)算法,将图像分解为shading(illumination) image 和 reflectance(albedo) image,计算图像的reflectance image。 Reflectance Image 是指在变化的光照条件下能够维持不变的图像部分...

  • 题目:面试题39. 数组中出现次数超过一半的数字 数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。 你可以假设数组是非空的,并且给定的数组总是存在多数元素。 示例 1: 输入: [1, 2, 3, 2, 2, 2, 5, 4, 2] 输出: 2 限制: 1 <= 数组长度 <= 50000 解题: cl...

  • 题目:二叉搜索树的后序遍历序列 输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true,否则返回 false。假设输入的数组的任意两个数字都互不相同。 参考以下这颗二叉搜索树:      5     /    2   6   /  1   3示例 1: 输入: [1,6,3,2,5] 输出...

  • 具体过程为: ① 通过相机标定方法,预先计算相机的内参矩阵; ② 相邻帧特征点匹配,并结合内参矩阵计算本征矩阵; ③ 本征矩阵分解获得相机的外参矩阵[R | T],最终的相机移动距离等于矩阵T的Frobenius范数。 #include #include

  • 题目:二叉树中和为某一值的路径 输入一棵二叉树和一个整数,打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。 示例: 给定如下二叉树,以及目标和 sum = 22,               5              /             4   8    ...

  • begin函数: 函数原型: iterator begin(); const_iterator begin(); 功能: 返回一个当前vector容器中起始元素的迭代器。 end函数: 函数原型: iterator end(); const_iterator end(); 功能: 返回一个当前vector容器中末尾元素的迭代器。...

  • 文章目录前言vector的核心接口vector push_back实现vector 的 Allocatorvector 的 push_back总结...

  • 给定一个二叉树,返回其按层次遍历的节点值。 (即逐层地,从左到右访问所有节点)。 例如: 给定二叉树: [3,9,20,null,null,15,7] 3 / 9 20 / 15 7 返回其层次遍历结果: [ [3], [9,20], [15,7] ] 方法一(非递归) 二叉树的层次遍历即二叉树的广度遍历,可以使...