[백준/Python] 모든 순열 10974

알고리즘 분류 : 백트래킹, 브루트포스

시간 복잡도 : O(N^N)

'''
Condition
    - TL : 1s (약 2000만)
    - ML : 256mb (약 64*10만)
    - 1<=N<=8

Question
    - 1부터 n까지 수로 이루어진 순열을 사전순으로 출력

Access
    - 전형적인 백트래킹 문제
'''

#input data
n=int(input())
sqc=[]

#define function
def back(cnt):
    #end condition : 
    if cnt ==n: # 순열의 size가 n이 된다면 print
        print(*sqc)
    #순열 만들기    
    for i in range(1,n+1):
        if i not in sqc: # sqc list에 i가 없다면 append함
            sqc.append(i)
            back(cnt+1)
            sqc.pop()    # i를 넣기 전 상태로 돌아가기 위해 pop해줌

#main()
back(0)