46. Permutations

문제

Given a collection of distinct integers, return all possible permutations.

예시

Example:

Input: [1,2,3]
Output:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

풀이

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        
        n = len(nums)
        visited = [False for _ in range(n)]
        res = []
        
        def generate(current, visited):
            if len(current) == n:
                res.append(current[::])
                return
            
            for i in range(n):
                if not visited[i]:
                    current.append(nums[i])
                    visited[i] = True
                    generate(current, visited)
                    visited[i] = False
                    current.pop()
        generate([], visited)
    
        return res