n个不同整数的所有子集（递归输出）

题目描述

计算n个不同整数的所有子集

输入

第1行是一个整数m，表示随后有m组数据。 每组数据占一行，第一个整数n表示随后有n个不同的整数。

输出

对每组数据，输出这n个不同整数的不同组合，含空组合。每个组合输出前输出“–> ”。

要求必须按照上课讲的递归方法来写，先输出包含该元素的情况，再输出不包含的情况，这样才能保证输出顺序和标准答案一致。

样例

输入 2 2 1 2 3 1 2 3 输出 –> 1 2 –> 1 –> 2 –> –> 1 2 3 –> 1 2 –> 1 3 –> 1 –> 2 3 –> 2 –> 3 –>

代码

#include <cstring> #include <iostream> using namespace std; void subset(int list[], int tag[], int n,int len) //生成子集 共2^n个 { if (n == len) { cout << "-->"; for (int i = 0; i < len; i++) { if (tag[i] == 1) cout <<' '<< list[i]; } cout<<endl; return; } tag[n] = 1; subset(list, tag, n + 1,len); tag[n] = 0; subset(list, tag, n + 1,len); } int main() { //cout << "请您输入整数的个数:"; int m; cin>>m; while(m--) { int n; cin >> n; int *number = new int[n]; int *tag = new int[n]; for (int i = 0; i < n; i++) { cin >> number[i]; } // for (int i = 0; i < n; i++) // { // cout << number[i]; // } // cout<<endl; //memset(tag,1,sizeof(tag[0])*n); // for (int i = 0; i < n; i++) // { // cout << tag[i]<<endl; // } subset(number, tag, 0,n); } //system("pause"); return 0; }

运行结果