[알고리즘] Permutations

포인트

1. 순열을 구하는 건 정말 어려우면서도 싶습니다. 특히나 cpp, python 은 모두 순열을 구해주는 라이브러리가 있습니다. 하지만 중간에 어떠한 조건을 주면 시간 초과가 나거나 하는 문제 등이 있어서 집적적으로 구해주는 방법도 알고 있으시면 좋을 것 같습니다. 

🧶문서는 항상 수정 될 수 있습니다. 비판은 환영합니다. 

python1

class Solution:
    def __init__(self) -> None:
        self.answer = []

    def go(self, cnt: int, nums, sel, visited):
        global answer
        if cnt == len(nums):
            self.answer.append(sel[:])
            return

        for ele in range(len(nums)):
            if visited[ele] == 0:
                visited[ele] = 1
                sel.append(nums[ele])
                self.go(cnt+1, nums, sel, visited)
                sel.pop()
                visited[ele] = 0

    def permute(self, nums: List[int]) -> List[List[int]]:
        visited = [0]*len(nums)
        sel = []
        self.go(0, nums, sel, visited)
        return self.answer

python

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        from itertools import permutations
        answer = []
        for ele in list(permutations(nums)):
            answer.append(list(ele))
        return answer