Backtracking: 46. Permutations

46. Permutations

 

이 문제는 주어진 배열의 모든 순열(permutations)을 생성하는 문제입니다. 순열은 순서가 중요한 조합으로, 배열의 각 요소를 모든 가능한 순서로 나열해야 합니다.

---

풀이 접근

1. 백트래킹 사용:
   • 순열을 생성하기 위해 각 요소를 선택하고, 선택된 요소는 사용하지 못하도록 추적합니다.
   • 모든 요소가 사용되면 현재 조합을 결과에 추가합니다.
   • 탐색이 끝나면 선택을 취소(백트래킹)하고 다음 탐색을 진행합니다.
2. 중복된 숫자가 없으므로 단순한 추적만 필요:
   • 중복 제거를 위해 추가적인 set이나 중복 확인이 필요하지 않습니다.
3. 재귀적으로 순열 생성:
   • 재귀를 통해 가능한 모든 순서를 탐색하며 결과를 생성합니다.

 

 

https://youtu.be/s7AvT7cGdSo?si=tUsr_udpq0Mpu_vA

 

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        res = []  # 최종 결과를 저장할 리스트

        # base case: nums의 길이가 1인 경우, 그 자체로 하나의 순열이 됨
        if len(nums) == 1:
            return [nums.copy()]  # nums의 복사본을 리스트로 반환 (nums는 가변 객체이므로 복사 필요)

        # 모든 숫자에 대해 순열 생성
        for i in range(len(nums)):
            n = nums.pop(0)  # 첫 번째 숫자를 꺼내어 저장
            perms = self.permute(nums)  # 나머지 숫자로 재귀적으로 순열 생성

            # 재귀 호출에서 반환된 순열에 꺼낸 숫자 n을 추가
            for perm in perms:
                perm.append(n)  # 현재 숫자를 각 순열에 추가

            res.extend(perms)  # 결과 리스트에 현재 순열들을 추가

            nums.append(n)  # 꺼냈던 숫자를 리스트의 맨 뒤에 다시 추가 (원상복구)

        return res  # 최종 결과 반환

 

코드 설명

1. res 초기화:
   • 최종적으로 반환할 순열 목록을 저장할 리스트.
2. Base Case:
   • 리스트 nums의 길이가 1이면, 그 자체로 순열을 구성할 수 있으므로 [nums.copy()]를 반환합니다.
   • nums.copy()를 사용하는 이유:
     • Python의 리스트는 가변 객체이므로, 참조를 공유하지 않도록 복사본을 반환해야 합니다.
3. 재귀적으로 순열 생성:
   • 리스트의 첫 번째 요소를 꺼내(nums.pop(0)) 현재 단계에서 처리할 숫자로 선택.
   • 나머지 숫자들로 순열을 생성하기 위해 self.permute(nums)를 호출.
4. 현재 숫자를 각 순열에 추가:
   • 재귀 호출에서 반환된 순열 목록(perms)에 현재 숫자 n을 추가.
   • 각 순열(perm)에 대해 perm.append(n)으로 숫자를 덧붙임.
5. 결과를 합치기:
   • res.extend(perms)를 통해 현재 단계에서 생성된 순열을 결과 리스트에 추가.
6. 원상복구:
   • nums.append(n)으로 꺼냈던 숫자를 다시 리스트의 끝에 추가하여 다음 반복을 위한 원래 상태로 복원.
7. 결과 반환:
   • 최종적으로 res 리스트를 반환하여 모든 가능한 순열을 반환.

 

장점과 단점

1. 장점:
   • 간결한 구현으로 순열 생성 가능.
   • 리스트 복사 및 재귀 호출을 통해 간단히 모든 경우를 처리.
2. 단점:
   • nums.pop(0)와 nums.append(n)으로 인해 리스트의 크기가 크면 성능 저하 가능.
   • Python의 리스트는 연결 리스트가 아니라 배열 기반이므로 pop(0)은 O(n)의 시간 복잡도를 가짐.

 

GPT 풀이

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        res = []  # 결과를 저장할 리스트
        used = [False] * len(nums)  # 각 숫자의 사용 여부를 추적

        # 백트래킹 함수 정의
        def backtrack(path):
            # 종료 조건: 경로 길이가 nums와 같으면 결과에 추가
            if len(path) == len(nums):
                res.append(path[:])  # path의 복사본 추가
                return
            
            # 숫자 선택
            for i in range(len(nums)):
                if not used[i]:  # 숫자가 아직 사용되지 않았다면
                    path.append(nums[i])  # 숫자 추가
                    used[i] = True  # 사용 표시
                    backtrack(path)  # 재귀 호출
                    path.pop()  # 추가한 숫자 제거 (백트래킹)
                    used[i] = False  # 사용 표시 해제
        
        # 백트래킹 시작
        backtrack([])
        return res

또는

def permute(nums):
    def backtrack(path, used):
        if len(path) == len(nums):
            res.append(path[:])
            return
        for i in range(len(nums)):
            if not used[i]:
                used[i] = True
                path.append(nums[i])
                backtrack(path, used)
                path.pop()
                used[i] = False
    res = []
    backtrack([], [False] * len(nums))
    return res

개선점

nums의 원소를 직접 사용하고, path와 방문 추적 리스트를 사용하는 방식으로 개선할 수 있습니다.

이는 pop(0)의 성능 문제를 해결합니다.

 

코드 설명

1. res:
   • 모든 가능한 순열을 저장할 리스트.
2. used:
   • 각 숫자가 현재 경로에서 사용되었는지 여부를 추적.
3. backtrack 함수:
   • 매개변수:
     • path: 현재까지 선택된 숫자의 경로.
   • 종료 조건:
     • 경로 길이가 nums와 같으면 결과에 추가.
   • 탐색:
     • 아직 사용되지 않은 숫자를 선택하여 경로에 추가.
     • 선택한 숫자로 재귀 호출.
     • 재귀 호출이 끝나면 숫자를 제거하고 사용 상태를 해제(백트래킹).

 

 

대안: 라이브러리 사용

Python에서는 **itertools.permutations**를 사용해 간단히 순열을 구할 수 있습니다:

from itertools import permutations

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

 

 

Visit = Set() 사용

아래는 visit = set()을 사용하여 중복 방지 및 방문 추적을 수행하는 방식으로 수정한 코드입니다. set은 Python에서 효율적으로 포함 여부를 확인할 수 있으므로 유용합니다.

 

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        res = []  # 결과를 저장할 리스트
        visit = set()  # 방문한 숫자를 추적하는 집합

        # 백트래킹 함수 정의
        def backtrack(path):
            # 종료 조건: 경로의 길이가 nums의 길이와 같으면
            if len(path) == len(nums):
                res.append(path[:])  # path의 복사본을 결과에 추가
                return

            # 숫자를 하나씩 탐색
            for num in nums:
                if num not in visit:  # 방문하지 않은 숫자만 처리
                    visit.add(num)  # 현재 숫자를 방문한 것으로 표시
                    path.append(num)  # 경로에 숫자를 추가
                    backtrack(path)  # 재귀 호출로 다음 숫자 탐색
                    path.pop()  # 경로에서 숫자를 제거 (백트래킹)
                    visit.remove(num)  # 방문 상태를 되돌림

        # 백트래킹 시작
        backtrack([])
        return res

 

코드 설명

1. res:
   • 최종 결과를 저장하는 리스트.
2. visit:
   • 이미 경로에 추가된 숫자를 추적하기 위한 집합.
   • set은 빠른 삽입, 삭제, 검색 (O(1))이 가능하여 방문 확인에 적합.
3. backtrack 함수:
   • 매개변수:
     • path: 현재까지 선택된 숫자를 저장하는 리스트.
   • 종료 조건:
     • path의 길이가 nums와 같으면 완성된 순열이므로 결과에 추가.
   • 탐색:
     • 모든 숫자를 확인하며, visit 집합에 없는 숫자를 추가.
     • 선택한 숫자로 재귀 호출.
     • 재귀 호출 후 숫자를 제거하여 원래 상태로 복원(백트래킹).
4. 백트래킹 실행:
   • 초기 path는 빈 리스트로 시작.
   • 모든 가능한 숫자를 탐색하여 순열 생성.

 

 

https://youtu.be/TSKMoC6wHJ4?si=MUk0QriimZ8mnDtm

 

내 코드

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        res = []

        def backtrack(subset, visited):
            if len(subset) > len(nums):
                return
            
            if len(subset) == len(nums):
                res.append(subset.copy())
                return

            for i in range(len(nums)):
                if i not in visited:
                    subset.append(nums[i])
                    visited.append(i)
                    backtrack(subset, visited)
                    subset.pop()
                    visited.pop()


        backtrack([], [])
        return res

 

---------------------------------

 

아직 이거는 이해 안감

 

https://youtu.be/FZe0UqISmUw?si=ARzGwCDc40tzaoLC