普通方法：

引例：如果题目不要求输出方案必须升序

填坑，从填1个坑到填n个坑。
坑可以随便填，比如第1个坑选了2之后，第2个坑可以填1（非升序），也可以填3（升序）

代码：

import java.io.*;
import java.math.BigInteger;
import java.text.ParseException;
import java.text.SimpleDateFormat;
import java.util.*;
import java.util.stream.Collectors;public class Main
{static PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));static int N = 100010;static int num[] = new int[N];static boolean state[] = new boolean[N];static int n;static void dfs(int pos,int tar){if(pos == tar + 1){for(int i = 1 ; i <= tar ; i ++)  pw.print(num[i] + " ");pw.println();return;}for(int i = 1 ; i <= n ; i ++){if(!state[i]){num[pos] = i;state[i] = true;dfs(pos + 1, tar);num[pos] = 0;state[i] = false;}}}public static void main(String[] args) throws NumberFormatException, IOException{n = rd.nextInt();pw.println(); // 不取for(int i = 1 ; i <= n ; i ++)  dfs(1,i);pw.flush();}
}class rd
{static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));static StringTokenizer tokenizer = new StringTokenizer("");static String nextLine() throws IOException { return reader.readLine(); }static String next() throws IOException{while(!tokenizer.hasMoreTokens())  tokenizer = new StringTokenizer(reader.readLine());return tokenizer.nextToken();}static int nextInt() throws IOException { return Integer.parseInt(next()); }static double nextDouble() throws IOException { return Double.parseDouble(next()); }static long nextLong() throws IOException { return Long.parseLong(next()); }static BigInteger nextBigInteger() throws IOException{BigInteger d = new BigInteger(rd.nextLine());return d;}
}class math
{int gcd(int a,int b){if(b == 0)  return a;else return gcd(b,a % b);}int lcm(int a,int b){return a * b / gcd(a, b);}// 求n的所有约数List get_factor(int n){List a = new ArrayList<>();for(long i = 1; i <= Math.sqrt(n) ; i ++){if(n % i == 0){a.add(i);if(i != n / i)  a.add(n / i);  // // 避免一下的情况：x = 16时，i = 4 ，x / i = 4的情况，这样会加入两种情况  ^-^复杂度能减少多少是多少}}// 相同因子去重，这个方法，完美a = a.stream().distinct().collect(Collectors.toList());// 对因子排序（升序）Collections.sort(a);return a;}// 判断是否是质数boolean check_isPrime(int n){if(n < 2) return false;for(int i = 2 ; i <= n / i; i ++)  if (n % i == 0) return false;return true;}
}class PII implements Comparable
{int x,y;public PII(int x ,int y){this.x = x;this.y = y;}public int compareTo(PII a){if(this.x-a.x != 0)return this.x-a.x;  //按x升序排序else return this.y-a.y;  //如果x相同，按y升序排序}
}class Edge
{int a,b,c;public Edge(int a ,int b, int c){this.a = a;this.b = b;this.c = c;}
}

但是，题目要求输出所有升序方案

依旧是填坑，从填1个坑到填n个坑。
和上面不同的是，上面是第1个坑选了2之后，第2个坑还可以从2之前的数开始填坑，现在是第1个坑选了2之后，第2个坑只能从大于2的数里选了。
即，当前的坑pos处填了num，则填下一个坑pos+1时，只能从大于num的数里选择填坑。

解决办法：dfs里加一个start，选数的时候，只能从start之后的数里面选择

总结：dfs需要四个变量记录当前状态：
当前位于的坑pos，当前可以选的最小数字start，当前的目标总坑数tar，当前已经填的坑数组num[]。

题目AC代码：

import java.io.*;
import java.math.BigInteger;
import java.text.ParseException;
import java.text.SimpleDateFormat;
import java.util.*;
import java.util.stream.Collectors;public class Main
{static PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));static int N = 100010;static int num[] = new int[N];static boolean used[] = new boolean[N]; //判断数字有没有用过static int n;static void dfs(int pos, int startindex ,int tar){if(pos == tar + 1){for(int i = 1 ; i <= tar ; i ++)  pw.print(num[i] + " ");pw.println();return;}// 枚举pos位置可以填哪些数for(int i = startindex ; i <= n ; i ++){if(!used[i]){num[pos] = i; // pos位置填iused[i] = true; // i标记为已使用过dfs(pos + 1, i + 1, tar); // 进入下一层num[pos] = 0;used[i] = false;}}}public static void main(String[] args) throws NumberFormatException, IOException{n = rd.nextInt();pw.println(); // 不取for(int i = 1 ; i <= n ; i ++)  dfs(1,1,i);pw.flush();}
}class rd
{static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));static StringTokenizer tokenizer = new StringTokenizer("");static String nextLine() throws IOException { return reader.readLine(); }static String next() throws IOException{while(!tokenizer.hasMoreTokens())  tokenizer = new StringTokenizer(reader.readLine());return tokenizer.nextToken();}static int nextInt() throws IOException { return Integer.parseInt(next()); }static double nextDouble() throws IOException { return Double.parseDouble(next()); }static long nextLong() throws IOException { return Long.parseLong(next()); }static BigInteger nextBigInteger() throws IOException{BigInteger d = new BigInteger(rd.nextLine());return d;}
}class math
{int gcd(int a,int b){if(b == 0)  return a;else return gcd(b,a % b);}int lcm(int a,int b){return a * b / gcd(a, b);}// 求n的所有约数List get_factor(int n){List a = new ArrayList<>();for(long i = 1; i <= Math.sqrt(n) ; i ++){if(n % i == 0){a.add(i);if(i != n / i)  a.add(n / i);  // // 避免一下的情况：x = 16时，i = 4 ，x / i = 4的情况，这样会加入两种情况  ^-^复杂度能减少多少是多少}}// 相同因子去重，这个方法，完美a = a.stream().distinct().collect(Collectors.toList());// 对因子排序（升序）Collections.sort(a);return a;}// 判断是否是质数boolean check_isPrime(int n){if(n < 2) return false;for(int i = 2 ; i <= n / i; i ++)  if (n % i == 0) return false;return true;}
}class PII implements Comparable
{int x,y;public PII(int x ,int y){this.x = x;this.y = y;}public int compareTo(PII a){if(this.x-a.x != 0)return this.x-a.x;  //按x升序排序else return this.y-a.y;  //如果x相同，按y升序排序}
}class Edge
{int a,b,c;public Edge(int a ,int b, int c){this.a = a;this.b = b;this.c = c;}
}

y总的思路：

枚举每个位置，看看该位置填不填数，填的话填哪些数字

AC代码：（自己写的！！！）
 

import java.io.*;
import java.math.BigInteger;
import java.text.ParseException;
import java.text.SimpleDateFormat;
import java.util.*;
import java.util.stream.Collectors;public class Main
{static PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));static int N = 100010;static List num = new LinkedList<>();static boolean state[] = new boolean[N];static boolean used[] = new boolean[N];static int n;// dfs存的状态：当前第pos位置static void dfs(int pos){if(pos == n + 1){for(int i = 1 ; i <= n ; i ++)   if(state[i]) pw.print(i + " ");  // state[i]为true，即该位置选了，需要输出pw.println();return;}// pos位置不选state[pos] = false;dfs(pos + 1);state[pos] = true;// pos位置选state[pos] = true;dfs(pos + 1);state[pos] = false;}public static void main(String[] args) throws NumberFormatException, IOException{n = rd.nextInt();dfs(1);pw.flush();}
}class rd
{static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));static StringTokenizer tokenizer = new StringTokenizer("");static String nextLine() throws IOException { return reader.readLine(); }static String next() throws IOException{while(!tokenizer.hasMoreTokens())  tokenizer = new StringTokenizer(reader.readLine());return tokenizer.nextToken();}static int nextInt() throws IOException { return Integer.parseInt(next()); }static double nextDouble() throws IOException { return Double.parseDouble(next()); }static long nextLong() throws IOException { return Long.parseLong(next()); }static BigInteger nextBigInteger() throws IOException{BigInteger d = new BigInteger(rd.nextLine());return d;}
}class math
{int gcd(int a,int b){if(b == 0)  return a;else return gcd(b,a % b);}int lcm(int a,int b){return a * b / gcd(a, b);}// 求n的所有约数List get_factor(int n){List a = new ArrayList<>();for(long i = 1; i <= Math.sqrt(n) ; i ++){if(n % i == 0){a.add(i);if(i != n / i)  a.add(n / i);  // // 避免一下的情况：x = 16时，i = 4 ，x / i = 4的情况，这样会加入两种情况  ^-^复杂度能减少多少是多少}}// 相同因子去重，这个方法，完美a = a.stream().distinct().collect(Collectors.toList());// 对因子排序（升序）Collections.sort(a);return a;}// 判断是否是质数boolean check_isPrime(int n){if(n < 2) return false;for(int i = 2 ; i <= n / i; i ++)  if (n % i == 0) return false;return true;}
}class PII implements Comparable
{int x,y;public PII(int x ,int y){this.x = x;this.y = y;}public int compareTo(PII a){if(this.x-a.x != 0)return this.x-a.x;  //按x升序排序else return this.y-a.y;  //如果x相同，按y升序排序}
}class Edge
{int a,b,c;public Edge(int a ,int b, int c){this.a = a;this.b = b;this.c = c;}
}