842. Arrange numbers

subject

Given an integer n, The digital 1∼n In a row , There will be many ways to arrange .

Now? , Please output all the arrangement methods in dictionary order .

Input format
All in one line , Contains an integer n.

Output format
Output all permutation schemes in dictionary order , One line for each scheme .

Data range
1≤n≤7
sample input ：
3
sample output ：
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

Ideas

dfs+ to flash back

Code

#include <iostream>

using namespace std;

const int N = 10;
int n, path[N];// Store the currently inserted number 
bool s[N];// Tag array , The tag subscript is i Has the number of been used 

void dfs(int cur)
{
    
    if(cur > n)// If n All positions have been inserted , here cur by n+1, Because array subscripts from 1 Start 
    {
    
        for(int i = 1; i <= n; i++)printf("%d ",path[i]);
        puts("");
        return;
    }
    // Traverse all numbers , Find out the unused numbers 
    for(int i = 1; i <= n; i++)
    {
    
        if(!s[i])// If the first i Numbers not used 
        {
    
            s[i] = true;// Mark the i Numbers have been used 
            path[cur] = i;// The first i Insert numbers into the current array of numbers 
            dfs(cur+1);// Continue to search deeply for the number that can be inserted into the next position 
            s[i] = false;// Restore the scene , take i Mark as unused 
        }
    }
}

int main()
{
    
    cin >> n;
    dfs(1);
    
    return 0;
}