LeetCode 46(Permutations, Python)

1. 문제 링크

• Permutations - LeetCode

Permutations - LeetCode

2. 문제 설명

• [1,2,3] 이 주어지면 이 수들로 가능한 모둔 순열(중복X, 순서 구분O)을 반환하는 문제
• 예시) [1,2,3]이 주어지면 [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

3. 처음 풀이

• 전형적인 백트래킹
• [1,2,3]을 순회하며 temp = []에 원소가 이미 들어있지 않다면 추가.
• temp의 원소가 3개가 되면 답지 ans=[]에 temp 추가.
• temp에 대해 재귀함수 처리, 답이 아니라면 temp.pop()하여 이전부터 다시 탐색

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

        def helper(temp, cur_nums):
            if len(temp) == len(nums):
                ans.append(temp[:])
                return
            else:
                for num in nums:
                    if num not in temp:
                        temp.append(num)
                        helper(temp, nums)
                        temp.pop()

        helper([],nums)

        return ans

4. 다른 풀이

• 인수에 nums, path, res를 넣는다. 
• nums의 i번째 요소를 path에 추가하고, 
• nums에서 i번째 요소만 제외한 nums를 인수로 넣어 재귀를 때린다. 
• nums는 하나씩 줄어들고 path는 하나씩 늘어난다.
• nums가 비어서 None이면 res에 현재 path를 추가한다. 

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        res = []
        self.dfs(nums, [], res)
        return res

    def dfs(self, nums, path, res):
        if not nums:
            res.append(path)
            #return # backtracking
        for i in range(len(nums)):
            self.dfs(nums[:i]+nums[i+1:], path+[nums[i]], res)

5. 배운 점

• 이제 백트래킹에 조금 익숙해질 수 있었다.