2628: 回溯法-子集问题
金币值：3
定数：8
时间限制：1.000 s
内存限制：128 M
正确：3
提交：3
正确率：100.00% 命题人：
题目描述
输入一个整数n表示有n(1<=n<=20)种不同的物品，要求输出这些物品的所有可能子集（如果子集中有第i个物品，则在对应的位置上输出1，否则在对应的位置上输出0；另外子集对应的二进制数要求从小到大输出，以保证答案唯一）
测试代码 复制
#include <stdio.h>
int n;//存储物品个数
int x[21]; //当前解，0号单元不存储有效数据
void output() {
int i;
for(i=1; i<=n; i++) {
printf("%d ",x[i]);
}
printf("\n");
}
void backtrack(int i) { // 搜索第i层结点
if(i>n) { //到达叶结点考虑结束本次递归
output();
} else {
}
}
int main(void) {
scanf("%d",&n);
backtrack(1);
return 0;
}输入格式
第1行输入一个整数
输出格式
后面各行依次从小到大输出子集对应的二进制数
输入样例 复制
3输出样例 复制
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1