C++递归求解N个元素的所有子集

这是之前视频面试时的一道编程题，题目是：求解N个元素的所有子集，如，输入{1,2,3}，输出{1,2,3,12,13,23,123}

面试官要求十分钟内写出来，当时有点小紧张，对递归也不是太熟，所以只写了一半，没有完成。但是思路是有的，而且是正确的，在面试结束后，花了将近10分钟的时间，将程序写了出来，思路如下：

看到题目，很快就想到了使用递归回溯的方法，

先输出长度为1的所有子集：1 ， 2， 3

输出长度为2的所有子集：12 ， 13， 23 

输出长度为3的所有子集：123

代码如下，自认为没什么问题了，第一次写，排版什么的都没做好，主要还是给自己做回顾用，如果有幸这篇文章被您所看到，有问题请不吝赐教。

#include <iostream>
#include <vector>
using namespace std;
int length,n;
vector<vector<int>> ans;
void find(vector<int> &a,vector<int> &t,int index){
if(t.size() == length){	//长度为指定长度时，保存到ans后，返回，结束这一次递归
ans.push_back(t);
return;
}
for(int i=index;i<n;i++){
t.push_back(a[i]);
find(a,t,i+1);
t.pop_back();	//回溯
}
}
int main()
{
cin>>n;
vector<int> a(n,0),t;
for(int i=0;i<n;i++)
cin>>a[i];
for(int i=1;i<=n;i++){	//长度递增
length++;
find(a,t,0);
}
for(int i=0;i<ans.size();i++){
for(int j=0;j<ans[i].size();j++)
cout<<ans[i][j]<<" ";
cout<<endl;
}
return 0;
}

最后

以上就是靓丽春天为你收集整理的C++递归求解N个元素的所有子集的全部内容，希望文章能够帮你解决C++递归求解N个元素的所有子集所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。