[DFS, 백트래킹] 순열 구하기

arr = [1, 2, 3]

def dfs(arr, sol, visited):
    # Base Case
    if len(arr) == len(sol):
        print(sol)
        return
    
    for i in range(len(arr)):
        if not visited[i]:	# 노드에서 같은 원소가 중복되는 경우 - 백트래킹
            visited[i] = True
            sol.append(arr[i])
            dfs(arr, sol, visited)
            sol.pop()	#  노드에서 하나의 순열을 완성한 경우 - 백트래킹
            visited[i] = False

dfs(arr, [], [False]*len(arr))



# 실행 결과
# [1, 2, 3]
# [1, 3, 2]
# [2, 1, 3]
# [2, 3, 1]
# [3, 1, 2]
# [3, 2, 1]

백트래킹 조건

1. 노드에서 같은 원소가 중복되는 경우 

• 가능한 순열이 아니므로 백트래킹

2. 노드에서 하나의 순열을 완성한 경우 

• 하나의 해를 찾음. 다시 자신의 스택프레임으로 돌아왔다면 이전에 추가했던 원소를 다시 원래대로 돌려 놓는다.