One day per day hiho220 weeks Push Button I

description There are N buttons on the console. Each button needs to be pushed exactly once. Each time you may push several buttons simultaneous.

Assume there are 4 buttons. You can first push button 1 and button 3 at one time, then push button 2 and button 4 at one time. It can be represented as a string “13-24”. Other pushing ways may be “1-2-4-3”, “23-14” or “1234”. Note that “23-41” is the same as “23-14”.

Given the number N your task is to find all the pushing ways.

Enter An integer N. (1 <= N <= 8)

output Output the different pushing ways in lexicographical order.

For the same pushing way output the smallest string in lexicographical order as representative.

样输入 3 Sample output 1-2-3 1-23 1-3-2 12-3 123 13-2 2-1-3 2-13 2-3-1 23-1 3-1-2 3-12 3-2-1

###题意 Insert a "-" sign in the middle of the 1-n full array to output all the different strings.

###Idea: The data range of this question is only N <= 8, and it is required to output all solutions. It is easier to think of exhaustive/violent search. However, we should still estimate the upper bound of the number of solutions. Consider that each representation is a 1~N arrangement with several minus signs inserted, so the number of solutions does not exceed N! * 2^(N-1). When N=8, it is about 5000000, acceptable The specific method of dfs is to first enumerate the case starting with each number. After all the cases are enumerated, consider the "-" sign to be overwritten with numbers.

#include <bits/stdc++.h>

Using namespace std;

Const int maxn = 128;

Bool vis[maxn];
Char ans[maxn] = "-";

Void dfs(int ptr, int cnt, int n)
{
If (cnt == 0) {
For (int i = 1; i < ptr; ++i)
Cout << ans[i];
Cout << endl;
Return;
}
If (ans[ptr-1] == '-') { // enumeration starts with each number
For (int i = 1; i <= n; ++i) {
If (vis[i]) continue;
Vis[i] = true;
Ans[ptr] = i+'0';
Dfs(ptr+1,cnt-1,n);
Vis[i] = false; //backtracking
}
Return;
}
Ans[ptr] = '-'; //The previous position is already a number, then the current position can be placed with "-"
Dfs(ptr+1,cnt,n);
For (int i = ans[ptr-1]-'0'+1; i <= n; ++i) { //Overwrite the "-" with a number greater than the previous position
If (vis[i]) continue;
Vis[i] = true;
Ans[ptr] = i+'0';
Dfs(ptr+1,cnt-1,n);
Vis[i] = false; // backtracking
}
}


Int main()
{
Int n;
Cin >> n;
Dfs(1,n,n);
Return 0;
}