리트코드 - 순열

과정

• dfs로 푼 근거는? -> 순열은 가능한 모든 경우의 수를 그래프 형태로 나열한 결과라 할 수 있다.
• 재귀로 푼 근거는? -> 입력이 [1, 2, 3]로 주어졌을 때 [1, 2, 3]을 한번에 풀지 않고 [1], [2], [3]으로 작게 나누어 해결하기 위해서 재귀 사용.

재귀함수

• 자기 자신을 호출/재참조하는 함수이다.
• 주어진 문제를 똑같은 유형의 하위 문제로 나누어 해결한다.
• 어떤 조건(base case)을 마주칠 때까지 자기 자신을 호출한다.
• 복잡한 입력을 더 간단한 입력으로 분류하여 자기 자신을 호출 (recursion case)

풀이

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        result = []
        prev_elements = []
        
        def dfs(elements):
            # base case: 마지막 숫자인 경우 end
            if len(elements) == 0:
                result.append(prev_elements[:])

            # recursion case: 복잡한 입력을 간단하게 바꾸자
            for i in elements:
                next_elements = elements[:]
                next_elements.remove(i)

                prev_elements.append(i)
                dfs(next_elements)
                prev_elements.pop()

        dfs(nums)

        return result

reference

lucidmaj7 개발/일상 블로그 - 재귀함수

파이썬 알고리즘 인터뷰