📌👉

📌 순열

서로 다른 정수를 입력받아 가능한 모든 순열을 리턴하라

👉 풀이로직

'''
순열
서로 다른 정수를 입력받아 가능한 모든 순열을 리턴하라

Example 1:
Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Example 2:
Input: nums = [0,1]
Output: [[0,1],[1,0]]

Example 3:
Input: nums = [1]
Output: [[1]]
'''
from typing import List


def permute(nums: List[int]) -> List[List[int]]:
    results = []
    prev_elements = []

    def dfs(elements):
        # 리프 노드일때 결과 추가
        if len(elements) == 0:
            results.append(prev_elements[:])

        # 순열 생성 재귀 호출
        for e in elements:
            next_elements = elements[:]
            next_elements.remove(e)

            prev_elements.append(e)
            dfs(next_elements)
            prev_elements.pop()

    dfs(nums)
    return results


print(permute([1, 2, 3]))

다시 이제 dfs(next_elements) 로 바로 가게 됩니다.

elements 에는 왜 갑자기 2가 생겼을까요 ?

if len(elements) == 0 :
	results.append(prev_elements[:])

로 되어있는 부분에서 results 에 더하게 되고 ,

리스트 추가가 된 뒤 elements 에 있는 요소가 없으니깐 .

다시 되 돌아가게 된다.

이런식으로 되돌아 간다고 생각하면 된다.

prev_elements.pop() 을 해서 요소 하나씩 뺀다 .

반복문이 1부터 시작하는것이 모두 끝났기 때문에 이제

2 가 시작된다.

results 에 데이터를 추가했고 , for e in elements: 로 내려간다.

여기서 바로 dfs(next_elements) 로 내려가게 된다.

prev_elements.pop() 을 하게되면 , 3 이 빠지게 되면서 다시

for e in elements

로 가게 된다.

for e in elements 

에서 다시 바로 dfs(next_elements) 로 가게 되고

내려가서 prev_elements.pop() 이 실행이 되면서

prev_elements 에 있는 1 이 사라지면서 , 다시

for e in elements 로 가게 된다.

이제 다시 바로 dfs(next_elements) 로 내려가게 된다.

또다시 elements 에 이 생겨난 이유는 ??

모든 요소를 탐색한후 뒤로 되돌아가기 때문에 이전상태로 돌아가게 된다.

이제 다시 바로 dfs(next_elements) 로 내려가게 된다.

이제 result 에 들어가게 된다.

이제 다시 이전상태로 계속 돌아가게 된다.

prev_elements.pop() 으로 1 을 제거 하고 다시 for e in elements 로 올라가게 된다.

다시 이제 전전 상태로 돌아간다.

prev_elements.pop() 으로 인해서 2 가 사라진다.

이제 전전전 상태로 돌아가게 되고 ,

다시 prev_elements.pop() 으로 인해서 3이 사라진다.

끝.