[leetcode] 46. Permutations

파이썬 알고리즘 인터뷰 (박상길, 2020) 의 문제 풀이를 보다가 놓치기 쉬운 부분이 있어서 기록.
아래 코드에서

prev_elements.pop() 부분이 왜 필요한지 처음에 봐서는 이해가 가지 않았다. 하지만 DFS 코드는 모든 순회를 순차적으로 해나가는데 여기에서 하나의 리스트 prev_elements 만을 사용해서 정답을 기록하기 때문에 이 리스트에 앞에서 순회했던 값들이 여전히 남아 있으면 안된다. DFS 순회를 빠져나오는 시점에서 다시 새로운 순회를 해야할 때까지 이전의 순회를 pop() 해줄 필요가 있었던 것이다.
prev_elements 라는 단일 리스트를 쓰지 않고 좀 더 깔끔하게 짤 수 있는 방법이 있을 것 같다.

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        results=[]
        prev_elements = []
        def dfs(elements):
            if len(elements) == 0: # elements가 남아있지 않다면!
                results.append(prev_elements[:]) # 여기가 중요하다.참조되지 않도록 copy형식을 한다.
            
            for e in elements:
                next_elements = elements[:]
                next_elements.remove(e)

                prev_elements.append(e)
                dfs(next_elements)
                prev_elements.pop() # prev라는 리스트 하나만 쓰기 때문에 dfs나올때 pop 제거하면서 나와야 함 
        dfs(nums)
        return results