C++

$\color{gold}{— > 蓝桥杯辅导课题解}$

思路：

递归

$\color{#ff00ff}{图解分析：}$

时间复杂度：$O(n * 2^n)$

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 20;

int n;
int st[N]; // 状态，记录每个位置当前的状态，0表示还没考虑，1表示选它，2表示不选它

void dfs(int u) {
    if (u > n) { // 到达边界
        for (int i = 1; i <= n; i ++) // 输出这个方案
            if (st[i] == 1)
                cout << i << ' '; 
        cout << endl;        
        return;
    }

    // 分支的过程
    st[u] = 2;
    dfs(u + 1); // 第一个分支：不选
    st[u] = 0; // 恢复现场

    st[u] = 1;
    dfs(u + 1); // 第一个分支：选
    st[u] = 1; // 恢复现场
}

int main() {
    cin >> n;

    dfs(1);

    return 0;
}

$\small{分享：}$

$\large\color{blue}{— > C/C++输入字符串}$