JAVA ac代码:

import java.util.*;
import java.util.StringTokenizer;
import java.io.*;

public class Main {
    static int n;
    static boolean flag[];
    public static void main(String[] args) {
        n=in.nextInt();
        flag=new boolean[n+1];
        dfs(1);
        out.close();
    }

    private static void dfs(int i) {
        //终止条件:i>n的时候,已经处理完了1-n
        if(i>n) {
            for(int j=1;j<=n;j++) {
                //选了这个数
                if(flag[j]) {
                    out.print(j+" ");
                }
            }
            out.println();
            return;
        }
        //题目会先输出选0个的选项，所以要把不选的dfs放前面
        dfs(i+1);
        flag[i]=true;
        dfs(i+1);
        flag[i]=false;//回溯
    }


    static FastReader in=new FastReader();
    static PrintWriter out=new PrintWriter(System.out);
    static class FastReader{
        static BufferedReader br;
        static StringTokenizer st;
        FastReader(){
            br=new BufferedReader(new InputStreamReader(System.in));
        }
        String next() {
            String str="";
            while(st==null||!st.hasMoreElements()) {
                try {
                    str=br.readLine();
                }catch(IOException e) {
                    throw new RuntimeException(e);
                }
                st=new StringTokenizer(str);
            }
            return st.nextToken();
        }
        int nextInt() {
            return Integer.parseInt(next());
        }
        double nextDouble() {
            return Double.parseDouble(next());
        }
        long nextLong() {
            return Long.parseLong(next());
        }
    }
    
}