03/11 코딩테스트 문제풀이 - 46. Permutations (Leetcode) ⭐⭐⭐⭐⭐

문제

• Leetcode 알고리즘 문제
• 46. Permutations (Medium)
• 문제 내용 : [링크]
  

내가 작성한 코드

class Solution:
    def permute(self, nums):
        def backtrack(path):
            if len(nums)==len(path):
                result.append(path)
                return
            
            for x in nums:
                if x not in path:
                    path.append(x)
                    backtrack(path[:])
                    path.pop()
                    
        result = []
        backtrack([])
        return result

• nums가 주어졌을 때, 완전 탐색을 통해 nums로 만들 수 있는 순열(중복을 포함하지 않는 비복원추출)을 모두 구하는 문제이다.

• backtrack 함수를 사용하여, nums에 담긴 숫자를 차례로 하나씩 뽑아 만들 수 있는 모든 순열을 구현해준다.

• 먼저 len(nums)==len(path)인 경우, 모든 숫자를 추출한 경우이므로 result 에 path를 append 해 주고 return 해준다.

• len(nums)!=len(path) 인 경우, for문을 통해 nums에서 숫자를 하나씩 추출해준다. 이 때 이 숫자가 path에 있지 않은 경우, append 해 준다.

• 이후 다음 숫자를 path에 추가해주기 위해서 재귀함수 backtrack을 출력해준다. 이 때, append 된 path를 반영할 수 있도록 backtrack(path[:])을 실행해준다.

• 모든 backtrack이 끝난 후, return 되어 나간 후에는(result에 append 된 후에는) path.pop()을 해주어 그 다음 숫자에 대한 순열을 구해나간다.

• backtrack([])을 통해 첫 함수를 실행한다. 이후 result를 return한다.

⭐⭐⭐⭐⭐

• 완전탐색의 기초가 되는 아주 중요한 문제! 계속 반복해서 풀어보기.