Combinations 조합

✅ 개념 정리: Combination (조합)

• 조합(combination) = 특정 개수(k) 만큼만 고른 부분집합
• 순서 상관 없음
  • [1, 2] 와 [2, 1] → 같은 조합
• 조건: 집합에서 k개의 원소만 선택

---

📌 예시

n = 5, k = 2 → [1, 2, 3, 4, 5] 중에서 2개씩 고르는 조합

결과 (총 10개):

[1, 2], [1, 3], [1, 4], [1, 5], [2, 3], [2, 4], [2, 5], [3, 4], [3, 5], [4, 5]

---

💡 해결 방법 2가지

1. 백트래킹 (Backtracking) – 직접 조합을 구성

 

✅ combinations(n, k) – DFS + 백트래킹 방식 (브랜치 두 갈래로 분기)

 

# Given n numbers (1 - n), return all possible combinations
# of size k. (n choose k math problem).
# Time: O(k * 2^n)
def combinations(n, k):
    combs = []  # 결과 조합들을 담을 리스트
    helper(1, [], combs, n, k)  # 1부터 시작해서 재귀 탐색 시작
    return combs  # 완성된 조합 리스트 반환

def helper(i, curComb, combs, n, k):
    # 현재 조합이 k개를 모두 고른 경우 → 정답 후보로 추가
    if len(curComb) == k:
        combs.append(curComb.copy())  # 현재 조합을 복사해서 저장
        return  # 더 이상 진행할 필요 없음

    # i가 n보다 커지면 끝 → 숫자 초과로 종료 조건
    if i > n:
        return

    # decision to include i
    # 현재 숫자 i를 조합에 포함시키는 경우
    curComb.append(i)  # i를 현재 조합에 추가
    helper(i + 1, curComb, combs, n, k)  # 다음 숫자로 진행
    curComb.pop()  # 백트래킹: i를 제거하고 다음 분기 탐색

    # decision to NOT include i
    # 현재 숫자 i를 조합에 포함시키지 않는 경우
    helper(i + 1, curComb, combs, n, k)  # 다음 숫자로 바로 넘어감

 

✅ combinations2(n, k) – for-loop 기반의 조합 생성 (정석적 DFS 백트래킹)

# Time: O(k * C(n, k))
def combinations2(n, k):
    combs = []  # 결과 조합들을 담을 리스트
    helper2(1, [], combs, n, k)  # 1부터 시작해서 재귀 탐색 시작
    return combs  # 완성된 조합 리스트 반환

def helper2(i, curComb, combs, n, k):
    # 현재 조합이 k개를 모두 고른 경우 → 정답 후보로 추가
    if len(curComb) == k:
        combs.append(curComb.copy())  # 현재 조합을 복사해서 저장
        return  # 더 이상 진행할 필요 없음

    # i가 n보다 커지면 더 이상 선택할 수 없으므로 종료
    if i > n:
        return

    # 현재 위치 i부터 n까지 순차적으로 숫자를 선택하면서 진행
    for j in range(i, n + 1):
        curComb.append(j)  # 숫자 j를 현재 조합에 추가
        helper2(j + 1, curComb, combs, n, k)  # j 이후 숫자들로 재귀 탐색
        curComb.pop()  # 백트래킹: j를 제거하고 다음 숫자 시도

---

🔍 시간복잡도

• 전체 조합 수는 수학적으로 nCk = n! / (k!(n-k)!) 개
• 백트래킹 방식의 시간복잡도: O(k * nCk)
  (조합 수 × 조합 당 k개의 숫자 복사)

📌 두 코드 비교 요약

항목	combinations	combinations2
방식	이진 분기 (선택/비선택)	for문 기반 선택
재귀 깊이	최대 n	최대 k
직관성	단순하지만 브랜치 많음	정석적 조합 DFS
시간복잡도	O(k * 2^n)	O(k * C(n, k))