递归/回溯：subsets求子集

首页 > 递归/回溯：subsets求子集

递归/回溯：subsets求子集

前言

回溯法又称为试探法，但当探索到某一步时，发现原先选择达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法。

已知一组数(其中无重复元素)，求这组数可以组成的所有子集。结果中不可有无重复的子集。

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

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

以上的初始数组集合中，每一个数在产生的子集中都有两种可能：存在、不存在

那么最终的子集个数就为2^n,(n为初始数组的大小)

如果仅仅生成[1],[1,2],[1,2,3]这样的集合，那么该如何实现呢？

过程如下：

方法一：使用普通的循环

std::vector<std::vector<int> > get_subsets2(std::vector<int> num) { std::vector<std::vector<int> > result; //存放最终的结果std::vector<int> item; //存放临时数组for (int i = 0;i < num.size(); ++i) { item.push_back(num[i]);result.push_back(item);}return result;
}

方法二：使用回溯的递归实现

void generate(int i, std::vector<int> &num,std::vector<int> &item, std::vector<std::vector<int> > &result) { if (i >= num.size()) { //结束条件即为遍历到最后一个元素return ;}item.push_back(num[i]);result.push_back(item);generate(i + 1,num,item,result); //每一次对下标++
}std::vector<std::vector<int> > get_subsets(std::vector<int> num) { std::vector<std::vector<int> > result;std::vector<int> item;generate(0,num,item,result);return result;
}

那么接下来需要生成最终的2^3个数的子集

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

方法一：

回溯法生成子集，因为针对每一个元素，都只有两种可能性，存在于子集或者不存在于子集之中，那么针对以上两种可能性，都可以选择递归进行后续元素的放入，每种元素同样有两种可能性，存在或者不存在；

例如 [1,2,3…]

针对元素1，有两种可能性:

item = [1],后续继续按照两种可能进行下一个元素的存放: item = [1,2],item = [1] …

item = [],后续继续按照两种可能进行下一个元素的存放: item = [2],item = [] …

这个过程使用递归实现如下:

void generate2(int i, std::vector<int> &num,std::vector<int> &item, std::vector<std::vector<int> > &result) { if (i >= num.size()) { return;}/*两种可能：1. 放入当前元素2. 不放入当前元素*/item.push_back(num[i]);  //放入当前元素result.push_back(item);generate2(i+1, num, item, result); item.pop_back();// 不放入当前元素generate2(i+1, num, item, result);
}
/*method1*/
std::vector<std::vector<int> > get_subsets(std::vector<int> num) { std::vector<std::vector<int> > result;std::vector<int> item;result.push_back(item); //空元素提前放入generate2(0,num,item,result);return result;
}

方法二：

使用位运算符进行运算，过程如下：

因为针对每一种元素都有两种可能，存在或者不存在；那么这个状态可以用0或者1代替；

若一个集合有三个元素A, B, C，则3个元素有2^3 = 8 种组成集合的方式，用0-7表示这些集合。即从000-111这个二进制范围代替，每一位代表对应元素的存在状态，0代表该元素不放入集合，1代表该元素放入了集合，总共有2^n种状态。

构造A元素为100 = 4且1<<2 = 4 ，B元素为010 = 2且 1 << 1 = 2, C元素为001 = 1 且1 << 0 = 1，构造如下表格(表格中的按位与的结果并不是真正的与之后的数值，而是代表对应元素存在与否的真值):

集合	整数	A是否出现	B是否出现	C是否出现
{}	000=0	1 << 2 & 000 = 0	1 << 1 & 000 = 0	1 << 0 & 000 = 0
{C}	001=1	1 << 2 & 001 = 0	1 << 1 & 001 = 0	1 << 0 & 001 = 1
{B}	010=2	1 << 2 & 010 = 0	1 << 1 & 010 = 1	1 << 0 & 010 = 0
{B,C}	011=3	1 << 2 & 011 = 0	1 << 1 & 011 = 1	1 << 0 & 011 = 1
{A}	100=4	1 << 2 & 100 = 1	1 << 1 & 100 = 0	1 << 0 & 100 = 0
{A,C}	101=5	1 << 2 & 101 = 1	1 << 1 & 101 = 0	1 << 0 & 101 = 1
{A,B}	110=6	1 << 2 & 110 = 1	1 << 1 & 110 = 1	1 << 0 & 110 = 0
{A,B,C}	111=7	1 << 2 & 111 = 1	1 << 1 & 111=1	1 << 0 & 111 = 1

实现过程如下:

/*method2*/
std::vector<std::vector<int> > generate3(std::vector<int> &num){ std::vector<std::vector<int> > result;int all_set = 1 << num.size();for (int i = 0;i < all_set; ++i) { //遍历所有可能的结果std::vector<int> item;for (int j = 0;j < num.size(); ++j) { if (i & (1 << j)) {  //通过一一比对，核对最终j下标代表的元素是否存在item.push_back(num[j]);}}result.push_back(item);}return result;
}

测试代码如下:

#include 
#include 
#include /*
Subsets已知一组数(其中无重复元素)，求这组数可以组成的所有子集。 结果中不可有无重复的子集。
例如: nums[] = [1, 2, 3]
结果为: [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]
*/using namespace std;
void generate(int i, std::vector<int> &num,std::vector<int> &item, std::vector<std::vector<int> > &result) { if (i >= num.size()) { return ;}item.push_back(num[i]);result.push_back(item);generate(i + 1,num,item,result);
} std::vector<std::vector<int> > get_subsets2(std::vector<int> num) { std::vector<std::vector<int> > result;std::vector<int> item;result.push_back(item);for (int i = 0;i < num.size(); ++i) { item.push_back(num[i]);result.push_back(item);}return result;
}void generate2(int i, std::vector<int> &num,std::vector<int> &item, std::vector<std::vector<int> > &result) { if (i >= num.size()) { return;}item.push_back(num[i]);result.push_back(item);generate2(i+1, num, item, result);item.pop_back();generate2(i+1, num, item, result);
}/*method1*/
std::vector<std::vector<int> > get_subsets(std::vector<int> num) { std::vector<std::vector<int> > result;std::vector<int> item;result.push_back(item);generate2(0,num,item,result);return result;
}/*method2*/
std::vector<std::vector<int> > generate3(std::vector<int> &num){ std::vector<std::vector<int> > result;int all_set = 1 << num.size();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]);}}result.push_back(item);}return result;
}	int main(int argc, char const *argv[])
{ std::vector<int> num;std::vector<int> item;std::vector<std::vector<int>> result1;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);}result1= get_subsets(num);result2= generate3(num);cout << "method1 " << endl;for (int i = 0;i < result1.size(); ++i) { if (result1[i].size() == 0) { cout << "[]";}for (int j = 0;j < result1[i].size(); ++j) { std::cout << "[" << result1[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;
}

输出如下:

3
1 2 3
method1 
[]
[1] 
[1] [2] 
[1] [2] [3] 
[1] [3] 
[2] 
[2] [3] 
[3] 
method2 
[]
[1] 
[2] 
[1] [2] 
[3] 
[1] [3] 
[2] [3] 
[1] [2] [3]

可以看到递归回溯遍历的结果和位运算遍历到的结果输出顺序上是有差异的，递归回溯需要一直遍历到最终的尾元素，而位运算则是遍历过程中一个一个添加。

递归/回溯：subsets求子集

更多相关：

基于C++实现线程池加速

STL nth_element

c++11随机数产生器default_random_engine

Jsoncpp 在C++开发中的一些使用记录

递归/回溯：Combination Sum II数组之和

基于SfM计算相机姿态

剑指offer：面试题34. 二叉树中和为某一值的路径

vector容器 begin()与end()函数、front()与back()的用法

C++ STL: 容器vector源码分析

leetcode-102 二叉树的层次遍历

java 读取excel_Java12POI操作Excel

C++ 生成随机数

基于C++的本征图像分解(Intrinsic Image Decomposition)

剑指offer：面试题39. 数组中出现次数超过一半的数字

剑指offer：面试题33. 二叉搜索树的后序遍历序列