[LeetCode] 46. Permutations - 파이썬(Python)

문제 링크 : https://leetcode.com/problems/permutations/

Permutations - LeetCode

유형 : 백트래킹(BackTracking)

문제 설명

중복되지 않는 정수들이 담긴 배열 nums가 주어질 때, 만들 수 있는 모든 순열을 return하는 문제이다. 임의의 순서로 return하면 된다.

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]]

제한사항

• 1 <= nums.length <= 6
• -10 <= nums[i] <= 10
• nums의 모든 숫자들은 unique하다.

문제 풀이

성공 코드

from typing import List

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        self.nums = nums
        self.perms = []
        
        self.bt([])
        return self.perms
    
    def bt(self, crnt_set: List[int]):
        if len(crnt_set) == len(self.nums):
            self.perms.append(crnt_set.copy())
            return
        
        for num in self.nums:
            if num in crnt_set:
                continue
            
            crnt_set.append(num)
            self.bt(crnt_set)
            crnt_set.pop()

시간복잡도 : n*n! <= T(n) <= n^2*n!

공간복잡도 : O(n)