[LeetCode] 46. Permutations

 

접근

• 문제 자체는 기타 평이한 백트래킹 문제와 다를 바 없었지만 파이썬 리스트에 대한 개념 이해 부족으로 시간을 많이 씀
• 재귀 함수 내에서 리스트는 참조가 아닌 복사본을 활용하는 것을 권장
• 시간 버리는 문제라고 생각했는데 오히려 파이썬 리스트 좀더 깊게 알게 되는 계기가 되었음...😅

 

솔루션

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

        answer = []
        nums_length = len(nums)

        if nums_length == 1:
            answer.append(nums)
            return answer
        
        def backtrack(answer_list):
            if len(answer_list) == nums_length:
                answer.append(answer_list)
                return
            
            for i in nums:
                # only in case "i" is not visited
                if i not in answer_list:
                    tmp = answer_list.copy()
                    tmp.append(i)
                    backtrack(tmp)

        backtrack([])
        return answer