•
문제 링크 : 
LeetCodePermutations - LeetCode
•
문제 설명 : 제공된 요소를 사용하여 순열을 만들어 반환한다.
•
풀이 방법
◦
백 트래킹 방식을 사용하여, 순열을 구한다.
◦
모든 경우를 트리로 만들어, DFS 탐색을 한다고 생각하면 된다.
▪
가능한 문자를 붙여 계속 하위로 탐색한다.
▪
제공된 길이와 같다면 탐색을 중단한다.
•
시간복잡도 :
•
성공 코드
from typing import List
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
res = []
used = [False] * len(nums)
def backtrack(path, used, res):
# 길이가 맞는 경우
if len(path) == len(nums):
res.append(path[:])
return
for i in range(len(nums)):
# 사용되지 않은 문자일 경우
if not used[i]:
# 선택
path.append(nums[i])
used[i] = True
# 재귀 호출
backtrack(path, used, res)
# 백트래킹
path.pop()
used[i] = False
backtrack([], used, res)
return res
Python
복사