LeetCode 풀기 - 46. Permutations

46. Permutations

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

Permutations - LeetCode

문제)

솔루션1)

처음 문제 접근은 계속 nums의 index를 반복문으로 변경해가면서 풀려고 했더니 문제가 풀리지 않았다.

아래와 같이 그림을 그리면서 생각을 해보니 백트래킹 방식으로 문제를 쉽게 풀 수 있을 것이라는 생각이 들었다.

 

nums가 [1, 2, 3]을 예시로 설명한 그림이다.

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        # backtracking solution
        
        # 결과 리스트
        output = []

        def recursive(cur, remain):
            # termination condition
            if len(remain) == 0:
                output.append(cur)
                return

            for i, n in enumerate(remain):
                recursive(cur + [n], remain[0:i] + remain[i + 1:])

        recursive([], nums)
        return output

솔루션2)

python에서는 순열을 생성하는 함수를 제공한다.

permutations() 바로 사용한 솔루션이다.

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        return permutations(nums, len(nums))