Common method:
Example: If the topic does not require that the output scheme must be in ascending order
Filling pits, from filling 1 pit to filling n pits.
The pits can be filled casually. For example, after selecting 2 for the first pit, the second pit can be filled with 1 (in non-ascending order), or 3 (in ascending order).
code:
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(); // do not take
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);
}
// Find all divisors of n
List get_factor(int n)
{
List<Long> 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); // // Avoid the situation: when x = 16, i = 4, x / i = 4, this will add two situations ^-^How much can the complexity be reduced?
}
}
// Deduplication of the same factor, this method is perfect
a = a. stream(). distinct(). collect(Collectors. toList());
// Sort the factors (ascending)
Collections. sort(a);
return a;
}
// Check if it is a prime number
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<PII>
{
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; //Sort by x in ascending order
else return this.y-a.y; //If x is the same, sort by y in ascending order
}
}
class Edge
{
int a,b,c;
public Edge(int a ,int b, int c)
{
this.a = a;
this.b = b;
this.c = c;
}
}
However, the title requires output of all ascending schemes
It is still filling holes, from filling 1 hole to filling n holes.
The difference from the above is that after the first pit is selected as 2, the second pit can be filled from the number before 2. Now after the first pit is selected as 2, the second pit can only be filled from Choose from numbers greater than 2.
That is, if the current pit pos is filled with num, when filling the next pit pos + 1, you can only choose to fill the pit from the numbers greater than num.
Solution: Add a start to dfs. When selecting numbers, you can only choose from the numbers after start
Summary: dfs needs four variables to record the current state:
The pit pos currently located, the minimum number start that can be selected at present, the current target total pit number tar, and the currently filled pit array num[].
Subject AC code:
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]; //judging whether the number has been used
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;
}
// Enumerate which numbers can be filled in the pos position
for(int i = startindex; i <= n; i++)
{
if(!used[i])
{
num[pos] = i; // pos position fill i
used[i] = true; // i is marked as used
dfs(pos + 1, i + 1, tar); // enter the next layer
num[pos] = 0;
used[i] = false;
}
}
}
public static void main(String[] args) throws NumberFormatException, IOException
{
n = rd.nextInt();
pw.println(); // do not take
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);
}
// Find all divisors of n
List get_factor(int n)
{
List<Long> 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); // // Avoid the situation: when x = 16, i = 4, x / i = 4, this will add two situations ^-^How much can the complexity be reduced?
}
}
// Deduplication of the same factor, this method is perfect
a = a. stream(). distinct(). collect(Collectors. toList());
// Sort the factors (ascending)
Collections. sort(a);
return a;
}
// Check if it is a prime number
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<PII>
{
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; //Sort by x in ascending order
else return this.y-a.y; //If x is the same, sort by y in ascending order
}
}
class Edge
{
int a,b,c;
public Edge(int a ,int b, int c)
{
this.a = a;
this.b = b;
this.c = c;
}
}
y general idea:
Enumerate each position to see whether the position is filled with numbers, and what numbers to fill in if filled
AC code: (written by myself!!!)
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<Integer> num = new LinkedList<>();
static boolean state[] = new boolean[N];
static boolean used[] = new boolean[N];
static int n;
// The status of dfs storage: the current pos position
static void dfs(int pos)
{
if(pos == n + 1)
{
for(int i = 1 ; i <= n ; i + + ) if(state[i]) pw.print(i + " "); // state[i] is true, that is, the position is selected and needs to be output
pw. println();
return;
}
// pos position is not selected
state[pos] = false;
dfs(pos + 1);
state[pos] = true;
// pos position selection
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);
}
// Find all divisors of n
List get_factor(int n)
{
List<Long> 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); // // Avoid the situation: when x = 16, i = 4, x / i = 4, this will add two situations ^-^How much can the complexity be reduced?
}
}
// Deduplication of the same factor, this method is perfect
a = a. stream(). distinct(). collect(Collectors. toList());
// Sort the factors (ascending)
Collections. sort(a);
return a;
}
// Check if it is a prime number
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<PII>
{
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; //Sort by x in ascending order
else return this.y-a.y; //If x is the same, sort by y in ascending order
}
}
class Edge
{
int a,b,c;
public Edge(int a ,int b, int c)
{
this.a = a;
this.b = b;
this.c = c;
}
}