LeetCode 46번 Permutations

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

---

문제 파악

순열! 주어진 리스트에서 만들 수 있는 동일한 사이즈의 리스트를 모두 출력하는 문제다. 순열에 대해서 묻고 있다.

접근 방법

완전 탐색을 이용해서 문제를 풀면 될 것 같다. 그 중 백트래킹을 사용해도 좋을 것 같다. 순열은 구성요소가 같더라도 순서에 따라 순서가 같지 않으면 다른 순열이기 때문에 비록 중복되어서 없어지는 케이스는 없지만 완전 탐색을 통해서 풀면 좋을 것 같다.

코드 구현

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        ans = []

        def backtracking(curr):
            if len(curr) == len(nums):
                ans.append(curr[:])
                return

            for num in nums:
                if num not in curr:
                    curr.append(num)
                    backtracking(curr)
                    curr.pop()

        backtracking([])
        return ans