greentea31's Note

https://leetcode.com/problems/permutations/

풀이 과정

주어진 리스트의 순열을 구하는 문제이다.

itertools 모듈의 permutation 함수를 사용하면 문제를 쉽게 해결할 수 있다. 또한, DFS로도 순열을 생성할 수 있다.

https://greentea31.tistory.com/110?category=939228 

위의 재귀로 순열을 구현하는 예제가 일종의 dfs - backtracking으로 순열을 구현한 것이다.

재귀 1의 소스코드에서, answer.append(output)을 사용하면 맨 마지막 output이 중복 저장되므로

1. answer.append(output[:])

2. answer.append([i for i in output])

3. import copy

    answer.append(copy.deepcopy(output))

등을 이용해주어야 한다.  위의 2방법은 객체 내의 내부 객체까지는 복사되지 않는 반면, deepcopy를 사용하면 깊은 복사가 되어 내부 객체까지 완벽히 복사된다. 이 문제에서는 리스트 내의 리스트까지 존재하지는 않으므로 위의 2방법을 사용해도 된다.

소스 코드

재귀 1

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        length = len(nums)
        output = [-1 for _ in range(length)]
        answer = []
        discovered = collections.defaultdict(bool)
        
        def go(index, length):
            if index == length:
                answer.append(output[:])  # answer.append(output) 사용시 맨 마지막 output값 중복 저장됨.
                return
            
            for num in nums:
                if not discovered[num]:
                    discovered[num] = True
                    output[index] = num
                    go(index+1, length)
                    discovered[num] = False
        
        go(0, length)
        return answer

재귀 2

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        results = []
        prev_elements = []  # 이미 순열에 넣은 원소의 집합
        
        def dfs(elements):
            if len(elements) == 0:  # 모든 원소를 다 넣었으면 결과 값에 넣는다.
                results.append(prev_elements[:])
                # [:]가 없으면 prev_elements가 변경되면서 results에 들어갔던 값들도 변경된다.
            
            for ele in elements:
                prev_elements.append(ele)
                #  next_elements는 앞으로 순열에 넣어야 할 원소의 집합
                next_elements = elements[:]
                next_elements.remove(ele)
                
                dfs(next_elements)
                prev_elements.pop()
        
        dfs(nums)
        return results

itertools

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        return list(itertools.permutations(nums))