[LeetCode] 46. Permutations (Medium, Python)

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

LeetCode - The World's Leading Online Programming Learning Platform

 

아이디어

순열을 구하는 문제였다!

두 가지 방법으로 풀었다.

1. 파이썬 제너레이터 사용

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        
        def helper(prefix, num):
            if not num:
                yield prefix

            for i, n in enumerate(num):
                yield from helper(prefix + [n], num[:i]+num[i+1:])

        return list(helper([], nums))

 

2. DFS 사용

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        answer = []
        def dfs(prefix, num):
            if not num:
                answer.append(prefix)
                return
            
            for i, n in enumerate(num):
                dfs(prefix + [n], num[:i]+num[i+1:])

        dfs([], nums)
        return answer

두 가지를 비교하면 DFS가 더 적은 빠른 것을 알 수 있다 :3