[Leetcode] 46. Permutations

문제

 

https://leetcode.com/problems/permutations/description/

Permutations - LeetCode

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

 

중복되지 않은 정수가 주어질 때 만들 수 있는 모든 순열을 만들어서 정답을 반환하라. 순서는 상관없음

 

Example 1:

Input	Output
nums = [1,2,3]	[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

 

Example 2:

Input	Output
nums = [0,1]	[[0,1],[1,0]]

 

 

문제풀이 코드

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        nums_length = len(nums)
        result = []
        visited = [False] * nums_length
        
        def dfs(arr):
            if len(arr) == nums_length:
                result.append(arr[:])
 
            for i in range(nums_length):
                if not visited[i]:
                    visited[i] = True
                    arr.append(nums[i])
                    dfs(arr)
                    arr.pop()
                    visited[i] = False
        dfs([])
        return result

백트래킹을 이용하여 문제 풀이

1. 방문체크를 하기위해 visited를 초기화해준다

2. 재귀함수를 통해 모든 경우를 탐색한다

    - 현재 위치가 방문한곳이 아닐때에만 dfs함수 호출

    - arr에 현재 값 삽입 

    - dfs에 값이 추가된 arr로 다시 호출한다

    - 호출한 dfs가 종료되면 arr에 들어간 값을 pop하고 visited[i]를 다시 방문할 수 있도록 False로 변경

    - arr의 길이가 nums_length와 같으면 result에 추가해준다

3. 모든 재귀함수가 종료되면 result를 반환한다