Permutation 순열

✅ 순열 (Permutation) 요약 정리:

• 정의:
  주어진 원소들을 모두 사용하여, 순서를 고려해 나열하는 것.
• 예시:
  {1, 2, 3}의 순열 →
  [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]
  총 3! = 6가지
• 순열 vs 조합
   

  구분	순열 (Permutation)	조합 (Combination)
  순서	중요함	중요하지 않음
  원소 사용	모두 사용함	일부만 사용할 수도 있음
  예시	(1,2,3), (1,3,2) 등	{1,2}, {2,3} 등

---

💡 수학 공식:

• n개의 서로 다른 원소를 모두 사용한 순열의 개수:
  n! (팩토리얼)
  예: 3! = 3 × 2 × 1 = 6

✅ 재귀 방식 permutationsRecursive(nums)

# 시간 복잡도: O(n^2 * n!)
def permutationsRecursive(nums):
    return helper(0, nums)

def helper(i, nums):
    # 베이스 케이스: 모든 숫자를 처리했으면 빈 리스트를 포함한 리스트를 반환
    if i == len(nums):
        return [[]]

    resPerms = []  # 최종 결과를 저장할 리스트

    # 먼저 다음 인덱스부터 가능한 순열들을 구함 (뒤쪽부터 순열 생성)
    perms = helper(i + 1, nums)

    # 재귀로부터 얻은 순열 리스트 각각에 대해 현재 숫자 nums[i]를 모든 위치에 삽입
    for p in perms:
        for j in range(len(p) + 1):
            # 원본 리스트를 복사 (in-place 변경 방지)
            pCopy = p.copy()
            # 현재 숫자 nums[i]를 가능한 모든 위치에 삽입
            pCopy.insert(j, nums[i])
            # 새로운 순열을 결과 리스트에 추가
            resPerms.append(pCopy)

    return resPerms  # 모든 가능한 순열 반환

 

✅ 반복 방식 permutationsIterative(nums)

# 시간 복잡도: O(n^2 * n!)
def permutationsIterative(nums):
    perms = [[]]  # 초기에는 빈 리스트 하나만 존재

    # 입력 숫자 하나씩 처리
    for n in nums:
        nextPerms = []  # 새로 만들어질 순열들을 담을 리스트

        # 기존 순열들에 대해 현재 숫자 n을 삽입
        for p in perms:
            for i in range(len(p) + 1):
                # 기존 순열을 복사
                pCopy = p.copy()
                # 현재 숫자 n을 가능한 모든 위치에 삽입
                pCopy.insert(i, n)
                # 새로운 순열을 nextPerms에 저장
                nextPerms.append(pCopy)

        # 다음 반복을 위해 새로 만든 순열들을 갱신
        perms = nextPerms

    return perms  # 최종 모든 순열 반환

 

✅ 순열 생성 – 백트래킹 방식 ( with set for visited )

from typing import List

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

        def backtrack(subset, visited: set):
            # 현재 순열(subset)의 길이가 nums와 같다면 하나의 순열이 완성된 것
            if len(subset) == len(nums):
                res.append(subset.copy())  # 순열을 복사해서 결과에 저장
                return

            # 아직 선택하지 않은 인덱스(i)에 대해 반복
            for i in range(len(nums)):
                if i not in visited:  # 이미 선택한 숫자는 건너뜀 (중복 방지)
                    # 현재 숫자 nums[i]를 부분 순열에 추가
                    subset.append(nums[i])
                    # 해당 인덱스를 방문한 것으로 표시
                    visited.add(i)  # set은 add()

                    # 다음 숫자를 선택하러 재귀 호출
                    backtrack(subset, visited)

                    # 백트래킹: 선택을 되돌려 다음 분기 탐색
                    subset.pop()         # 마지막에 넣은 숫자를 제거
                    visited.remove(i)    # 방문 표시도 해제, set은 remove()

        # 백트래킹 시작 (초기에는 빈 순열, 방문한 숫자 없음)
        backtrack([], set())  # visited를 set으로 초기화

        return res  # 모든 순열이 저장된 리스트 반환