사용 개념: 재귀와 백트래킹.

이 방법을 떠올리는 신호는 “가능한 배치·순서·선택을 모두 만들되, 규칙을 어기는 것은 빼라”는 문제다. 늘 같은 네 하위목표로 짠다.

  1. 상태 정하기: 지금까지 고른 것과, 다음에 고를 수 있는 것을 무엇으로 나타낼지 정한다.
  2. 기저 사례: 다 골랐을 때 결과를 기록하고 돌아간다.
  3. 고르고·들어가고·되돌리기: 후보마다 넣고(append), 더 들어가고(재귀), 뺀다(pop).
  4. 겹침 막기·가지치기: 같은 결과를 두 번 만들지 않게 하고, 답이 될 수 없는 가지는 건너뛴다.

문제 1 · 완전한 풀이

1부터 n까지에서 k개를 고르는 모든 조합을 만든다. n = 4, k = 2.

  1. 상태 정하기: 지금까지 고른 수 리스트 chosen, 그리고 다음에 볼 수 있는 가장 작은 수 start.
  2. 기저 사례: len(chosen) == k면 chosen[:]을 기록하고 돌아간다.
  3. 고르고·들어가고·되돌리기: start부터 n까지의 x마다 chosen.append(x), go(x + 1), chosen.pop().
  4. 겹침 막기·가지치기: 다음 호출이 x + 1부터 보므로 늘 커지는 순서로만 고른다. 그래서 (1, 2)와 (2, 1)처럼 순서만 다른 것이 두 번 나오지 않는다. k개짜리 묶음 하나를 줄 세우는 순서는 k!가지인데, 커지는 순서는 그중 하나뿐이다. 그래서 결과는 정확히 조합의 수 \(\binom{n}{k}\)(\(\binom{\ }{\ }\)은 위의 수만큼 있는 것에서 아래의 수만큼 고르는 경우의 수)개이고, n = 4, k = 2면 6개다.
def combos(n, k):
    out, chosen = [], []
    def go(start):
        if len(chosen) == k:
            out.append(tuple(chosen))
            return
        for x in range(start, n + 1):
            chosen.append(x)
            go(x + 1)
            chosen.pop()
    go(1)
    return out
# [(1,2), (1,3), (1,4), (2,3), (2,4), (3,4)]

다음 호출의 시작점이 무엇을 만들지 정한다. go(x + 1)이면 조합이고, go(x)면 같은 수를 다시 고르는 중복조합이다. 시작점 대신 아직 안 쓴 수를 모두 보면 순열이고, 늘 모든 수를 보면 중복순열이다. 이 넷을 가르는 두 질문은 순열·조합·중복조합 비교에 있다.

문제 2 · 마지막 하위목표를 채운다

양수 [2, 3, 5, 7] 중 몇 개를 골라 합이 10이 되는 경우의 수를 센다.

  1. 상태 정하기: 다음에 볼 번호 start와 남은 합 remain.
  2. 기저 사례: remain == 0이면 1을 돌려준다.
  3. 고르고·들어가고·되돌리기: start부터의 i마다 go(i + 1, remain - nums[i])의 결과를 더한다. 남은 합을 인자로 넘기므로 따로 되돌릴 리스트가 없다.
  4. 겹침 막기·가지치기: __
답

겹침 막기는 문제 1과 같이 i + 1부터 보기다. 가지치기는 수를 미리 정렬해 두고, nums[i] > remain이면 break한다. 뒤의 수는 더 커서 모두 넘치기 때문이다(모두 양수라서 쓸 수 있다). 답은 2개다: {3, 7}, {2, 3, 5}.

문제 3 · 하위목표 절반을 채운다

4 × 4 체스판에 퀸 4개를 서로 공격하지 못하게 놓는 방법의 수(N-Queen, n = 4)를 센다. 퀸은 같은 줄, 같은 칸(열), 같은 대각선을 공격한다.

  1. 상태 정하기: 한 줄에 퀸은 하나뿐이니 줄 r을 0부터 차례로 채운다. 이미 쓴 열 집합, 쓴 대각선 두 종류(r − c가 같은 칸들, r + c가 같은 칸들)의 집합을 둔다.
  2. 기저 사례: __
  3. 고르고·들어가고·되돌리기: 열 c마다 세 집합에 넣고, go(r + 1), 세 집합에서 뺀다.
  4. 겹침 막기·가지치기: __
답

  1. r == n이면 모든 줄에 퀸을 놓았으니 1을 돌려준다.

  2. 줄마다 하나씩만 놓으니 줄이 겹칠 일은 없다. 가지치기는 c가 열 집합에 있거나, r − c나 r + c가 대각선 집합에 있으면 그 c를 건너뛰는 것이다. 이미 공격받는 칸에 놓으면 그 아래를 볼 필요가 없다.

답은 2가지다. n = 1~8의 답은 1, 0, 0, 2, 10, 4, 40, 92다.

문제 4 · 혼자 풀기

괄호 n쌍으로 만들 수 있는 올바른 괄호 문자열을 모두 만든다. n = 3이면 몇 개인가?

답

상태는 (지금까지의 문자열, 연 괄호 수, 닫은 괄호 수)다. 길이가 2n이면 기록한다. 연 괄호가 n보다 적으면 “(“를 붙여 들어가고, 닫은 괄호가 연 괄호보다 적으면 “)”를 붙여 들어간다. 이 두 조건이 가지치기다. 짝이 안 맞는 문자열은 처음부터 만들지 않는다.

def parens(n):
    out = []
    def go(s, opened, closed):
        if len(s) == 2 * n:
            out.append(s)
            return
        if opened < n:
            go(s + "(", opened + 1, closed)
        if closed < opened:
            go(s + ")", opened, closed + 1)
    go("", 0, 0)
    return out

n = 3이면 5개다: ((())), (()()), (())(), ()(()), ()()(). 문자열을 새로 만들어 넘기므로(s + "(") 따로 되돌리지 않아도 된다.

가지치기 두 조건으로 만든 문자열은 재귀적 정의와 구조적 귀납법에서 세 규칙(빈 문자열, (s), st)으로 만든 균형 괄호와 정확히 같다. 그래서 n쌍이면 카탈란 수 \(\frac{1}{n+1}\binom{2n}{n}\)개다. n = 1, 2, 3, 4, 5이면 1, 2, 5, 14, 42개다.