[pta---- output full arrangement]

Please write the program before output n A full permutation of positive integers （n<10）, And pass 9 Test cases （ namely n from 1 To 9） Observe n Gradually increase the running time of the program .

Input format :

Input gives a positive integer n（<10）.

Output format ：

Output 1 To n The whole arrangement . One line for each arrangement , No spaces between numbers . The order of output is dictionary order , Sequence a1,a2,⋯,a**n In sequence b1,b2,⋯,b**n Before , If there is k bring a1=b1,⋯,a**k=b**k also a**k+1<b**k+1.

sample input ：

3

sample output ：

123
132
213
231
312
321

analysis ：

The permutation problem belongs to the category of backtracking algorithm , Backtracking algorithm can be used to better solve the arrangement problem . For backtracking algorithms , Summarized below ：

** What is backtracking algorithm ？** Backtracking algorithm can also be called backtracking search method , It's a way of searching . Backtracking is a byproduct of recursion , As long as there is recursion, there will be backtracking .
Backtracking is not an efficient algorithm . Because the essence of backtracking is exhaustive , Exhaust all possibilities , Then choose the answer we want , If you want to make backtracking more efficient , You can add some pruning operations , But it can't change the essence that backtracking is exhaustion . Since the efficiency of backtracking algorithm is so low , Why use backtracking algorithm ？ This is because we are solving problems , Some problems can be solved by violence , It is difficult to solve with efficient algorithm .
How to understand backtracking algorithm ？
The problems solved by backtracking algorithm can be abstracted into tree structure . Because the backtracking method solves the recursive search of subsets in the set , The size of the set constitutes the width of the tree , The depth of recursion , The depth of the tree .
Recursion must have termination conditions , So it must be a tree with limited height （N Fork tree ）.
Backtracking algorithm template ：

void backtracking( Parameters ) {
    
    if ( Termination conditions ) {
    
         Store results ;
        return;
    }

    for ( choice ： The elements in this layer set （ The number of children in a tree is the size of the set ）) {
    
         Processing nodes ;
        backtracking( route , Selection list ); //  recursive 
         to flash back , Cancel processing result 
    }
}

According to this question , Join in n = 3, Then the array is [1,2,3]

You can see the leaf node , It's where the fruit is harvested .
So when , It can be regarded as reaching the leaf node ？
When collecting an array of elements path The size reaches and nums When the array is the same size , Indicates that a full permutation has been found , It also means reaching the leaf node .

//  This indicates that a set of 
if (path.size() == nums.size()) {
    
    result.push_back(path);
    return;
}

used Array , It's actually recording this time path What elements are used in , An element in an arrangement can only be used once .

for (int i = 0; i < nums.size(); i++) {
    
    if (used[i] == true) continue; // path Elements already included in , Just skip 
    used[i] = true;
    path.push_back(nums[i]);
    backtracking(nums, used);
    path.pop_back();
    used[i] = false;
}

c++ The overall code is as follows ：

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
class Solution{
    
	private:
		vector<vector<int>> result;
		vector<int> path;
		void backtracking(vector<int>& num, vector<bool> used) {
    
			if (path.size() == num.size()) {
    
				result.push_back(path);
			}
			for (int i = 0; i < num.size(); i++) {
    
				if (i > 0 && num[i] == num[i-1] && used[i-1] == true) {
    
					continue;
				}
				if (used[i] == false)
			{
    
				used[i] = true;
				path.push_back(num[i]);
				backtracking(num,used);
				used[i] = false;
				path.pop_back();
			}
			}
		}
	public:
		vector<vector<int>>permuteUnique(vector<int>& nums) {
    
			result.clear();
			path.clear();
			sort(nums.begin(),nums.end());
			vector<bool> used(nums.size());
			backtracking(nums,used);
			return result;
		}
};
int main() {
    
	Solution Q;
	int n;
	cin>>n;
	vector<int> num(n);
	for (int i = 0; i < n; i++) {
    
		num[i] = i + 1;
	}
	vector<vector<int>>result;
	result = Q.permuteUnique(num);
	for (auto i = result.begin(); i != result.end(); i++) {
    
		for (auto j = (*i).begin(); j != (*i).end(); j++) {
    
			cout<<*j;
		}
		cout<<endl;
	}
}