递归实现指数型枚举

从 1∼n
这 n
个整数中随机选取任意多个，输出所有可能的选择方案。

输入格式
输入一个整数 n
。

输出格式
每行输出一种方案。

同一行内的数必须升序排列，相邻两个数用恰好 1
个空格隔开。

对于没有选任何数的方案，输出空行。

include [HTML_REMOVED]

int n;
bool vis[20];
void printSubset(int* subset, int size) {
for (int i = 0; i < size; i++) {
if (i > 0) printf(” “);
printf(“%d”, subset[i]);
}
printf(“\n”);
}

void dfs(int pos, int* subset, int size) {
if (pos > n) {
printSubset(subset, size);
return;
}

dfs(pos + 1, subset, size);

if (!vis[pos]) {
    vis[pos] = true;
    subset[size] = pos;
    dfs(pos + 1, subset, size + 1);
    vis[pos] = false;
}

}

int main() {
printf(“请输入一个1-15的数字:”);
scanf(“%d”, &n);
int subset[20];
dfs(1, subset, 0);
return 0;
}