[leetcode / 46] Permutations

in Problem Solving on leetcode


날짜: 2021년 8월 30일
카테고리: 그래프
태그: Medium, 46, 파이썬

leetcode 46 - Permutations

입출력 예시

예제 입력예제 출력
nums = [1,2,3][[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
nums = [0,1][[0,1],[1,0]]
nums = [1][[1]]

코드

class Solution:
    def permute(self, nums):
        answer = list()
        prev_elements = list()

        def dfs(elements):
            if len(elements) == 0:
                answer.append(prev_elements[:])

            for e in elements:
                next_elements = elements[:]
                next_elements.remove(e)

                prev_elements.append(e)
                dfs(next_elements)

                prev_elements.pop()
        dfs(nums)

        return answer
파이썬 알고리즘 인터뷰 12-3

풀이 과정

answer와 prev_elements 리스트 생성
dfs 중첩 함수 생성

  • 만약 elements의 길이가 0이라면 answer리스트에 prev_elements 리스트를 원소로 추가
    • (파이썬은 모든 객체를 참조하는 형태로 처리되므로 얕은 복사를 위해 [:]를 붙여준다.)
  • elements의 원소만큼 반복을 하는데
    • next_elements에 elements를 얕은 복사하고

    • next_elements에서는 e를 제거

    • 그리고 prev_elements에도 e를 제거 한 다음

    • next_elements를 dfs함수로 재귀

    • 그러고 pre_elements의 원소를 순서대로 pop한 뒤 다시 재귀

answer을 반환하면 순열들을 리스트 형태로 원소로 가진 리스트가 반환 됨

반성

  • 구현 함에 있어 조금의 오류는 나지만 그래도 조금씩 재귀를 활용해서 로직의 방향성을 맞춰 나가는 중이다.


© 2021. by hminkim