leetcode 46. Permutations 순열

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

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: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Example 2:

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

Example 3:

Input: nums = [1]
Output: [[1]]

 

 

아래처럼 DFS로 풀수 있는 문제이다.

 

주어진 리스트에서 탈출조건이 성립되면 retrun으로 나오지만, 아닌 경우에는 다음 index에 맞는 친구들을 끊임없이 대입하면 되는 문제. 

 

조금 개념 잡기에는 어렵지만, DFS를 몇번 사용하다보면 흔히 나오는 부분 이기 때문에 풀만하다.

 

 

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        
        def dfs(sub_list: List, remain_list: List):
            # print(sub_list)
            if len(nums) == len(sub_list):
                result.append(sub_list)
                return

            for i, value in enumerate(remain_list):
                # print(i, sub_list+[value], remain_list[:i] + remain_list[i+1:])
                dfs(sub_list+[value], remain_list[:i] + remain_list[i+1:])

        result = []
        dfs([], nums)
        return result