순열과 조합 구현 (Permutation and Combination)

순열(Permutation)은 순서를 구분해서 뽑는 것, 조합(Combination)은 순서를 무시하고 뽑는 것이다. 완전 탐색 문제에서 "가능한 모든 경우"를 만들어야 할 때 둘 중 무엇인지 판단하는 것이 첫 단추다.

파이썬은 itertools가 다 해주지만, 면접에서는 직접 구현할 수 있어야 하고 코딩테스트에서도 가지치기(pruning)를 넣으려면 직접 짜야 한다. 이 글은 라이브러리 사용법과 백트래킹 구현을 함께 다룬다.

순열과 조합의 차이

구분	순열 nPr	조합 nCr
순서	구분한다	무시한다
개수	n! / (n−r)!	n! / (r! × (n−r)!)
3개 중 2개	6가지	3가지
구현 차이	이미 쓴 원소만 제외	현재 인덱스 뒤에서만 고른다

백트래킹으로 만들어 나가기

직접 구현할 때는 하나씩 골라 넣고, 끝까지 가보고, 다시 빼내는 방식을 쓴다. 이것이 백트래킹이다. 트리를 그려보면 무슨 일이 일어나는지 한눈에 보인다.

라이브러리로 하기

from itertools import permutations, combinations, product, combinations_with_replacement

arr = [1, 2, 3]

list(permutations(arr, 2))
# [(1,2), (1,3), (2,1), (2,3), (3,1), (3,2)]   순열 6가지

list(combinations(arr, 2))
# [(1,2), (1,3), (2,3)]                        조합 3가지

list(product(arr, repeat=2))
# [(1,1), (1,2), ..., (3,3)]                   중복 순열 9가지

list(combinations_with_replacement(arr, 2))
# [(1,1), (1,2), (1,3), (2,2), (2,3), (3,3)]   중복 조합 6가지

네 가지를 표로 정리하면 이렇다.

구분	순서 구분	같은 원소 재사용	함수	3개 중 2개
순열	O	X	permutations	6
조합	X	X	combinations	3
중복 순열	O	O	product	9
중복 조합	X	O	combinations_with_replacement	6

직접 구현하기

def permute(arr, r):
    """순열 — 이미 쓴 원소만 건너뛴다."""
    result, path = [], []
    used = [False] * len(arr)

    def backtrack():
        if len(path) == r:
            result.append(path[:])        # 반드시 복사본. path는 계속 바뀐다
            return
        for i in range(len(arr)):
            if used[i]:
                continue
            used[i] = True
            path.append(arr[i])
            backtrack()
            path.pop()                    # 되돌리기
            used[i] = False

    backtrack()
    return result


def combine(arr, r):
    """조합 — 현재 인덱스 다음부터만 고른다. used 배열이 필요 없다."""
    result, path = [], []

    def backtrack(start):
        if len(path) == r:
            result.append(path[:])
            return
        for i in range(start, len(arr)):
            path.append(arr[i])
            backtrack(i + 1)              # i+1 — 앞으로만 간다
            path.pop()

    backtrack(0)
    return result

두 함수의 차이는 딱 두 군데다. 순열은 used 배열로 "이미 쓴 것"을 막고 매번 range(len(arr)) 전체를 돈다. 조합은 start부터만 돌아서 인덱스가 항상 증가하도록 강제한다. 그러면 (1,2)는 만들어지지만 (2,1)은 애초에 생기지 않는다.

중복을 허용하려면 조합에서 backtrack(i + 1)을 backtrack(i)로 바꾸면 중복 조합이 되고, 순열에서 used 검사를 빼면 중복 순열이 된다.

def combinations_with_limit(arr, r, limit):
    """합이 limit 이하인 조합만 찾는다."""
    result, path = [], []

    def backtrack(start, total):
        if total > limit:                 # 여기서 끊으면 아래 가지를 통째로 건너뛴다
            return
        if len(path) == r:
            result.append(path[:])
            return
        for i in range(start, len(arr)):
            path.append(arr[i])
            backtrack(i + 1, total + arr[i])
            path.pop()

    backtrack(0, 0)
    return result