题目描述

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

输入格式

输入一个整数n。

输出格式

每行输出一种方案。

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

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

本题有自定义校验器（SPJ），各行（不同方案）之间的顺序任意。

数据范围

1≤n≤15

输入样例：

3

输出样例：

3
2
2 3
1
1 3
1 2
1 2 3

原题链接

演示样例为3的dfs逻辑

dfs(u+1,state); dfs(u+1,state | 1 << u);

按位或

按位或运算符“|”是双目运算符。
其功能是参与运算的两数各对应的二进位相或。
只要对应的二个二进位有一个为1时，结果位就为1。
当参与运算的是负数时，参与两个数均以补码出现。
百科地址

参考文献

https://www.acwing.com/video/110/

C++ 代码

#include <bits/stdc++.h>
using namespace std;

int n;
void dfs(int u ,int state){
    if ( u == n){
        for(int i = 0;i < n; i ++){
            if((state >> i & 1) == 1){
                printf("%d ",i + 1);
            }
        }    
        puts("");
        return ;
    }
    dfs(u+1,state);
    dfs(u+1,state | 1 << u);
}
int main(){
    scanf("%d",&n);
    dfs(0,0);
}

Java 代码

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.StringTokenizer;

public class Main{
    static QuickInput in = new  QuickInput();
    static PrintWriter out = new PrintWriter(System.out);
    static int n;

    public static void dfs_2(int u,int st) {
        if (u == n){
            for (int i = 0; i < n; i++) {
                if ((st >> i & 1) == 1 )
                    out.print( i + 1 + " ");
            }
            out.println();
            return;
        }
        dfs_2(u+1,st);
        dfs_2(u+1,st | 1 << u);
    }

    public static void main(String[] args){
        n = in.nextInt();
        dfs_2(0,0);
        out.close();//不关闭，就会有些数据留在缓冲区
    }
}


class  QuickInput
{
    BufferedReader buf;
    StringTokenizer tok;
     QuickInput(){
        buf = new BufferedReader(new InputStreamReader(System.in));
    }
    boolean hasNext(){
        while(tok == null || !tok.hasMoreElements()){
            try{
                tok = new StringTokenizer(buf.readLine());
            }catch(Exception e){
                return false;
            }
        }
        return true;
    }
    String next(){
        if(hasNext()) return tok.nextToken();
        return null;
    }
    int nextInt(){
        return Integer.parseInt(next());
    }
    long nextLong(){
        return Long.parseLong(next());
    }
    double nextDouble(){
        return Double.parseDouble(next());
    }
    BigInteger nextBigInteger(){
        return new BigInteger(next());
    }
    BigDecimal nextBigDecimal(){
        return new BigDecimal(next());
    }
}

Java快速读写模板