백트래킹(Backtracking) 실전 풀이 전략 – N-Queen부터 순열/조합 생성까지

def backtrack(state, choices):
    # 기저 조건: 답을 찾았거나 탐색이 끝난 경우
    if is_solution(state):
        result.append(state[:])  # 현재 상태를 결과에 추가
        return

    for choice in choices:
        if is_valid(state, choice):   # 가지치기 조건
            state.append(choice)       # 선택
            backtrack(state, choices)   # 재귀 탐색
            state.pop()                # 되돌림 (backtrack)

def permutations(nums, r):
    """n개의 원소에서 r개를 뽑는 순열 생성"""
    result = []
    used = [False] * len(nums)  # 각 원소의 사용 여부 추적

    def backtrack(path):
        # 기저 조건: r개를 모두 선택했으면 결과에 추가
        if len(path) == r:
            result.append(path[:])
            return

        for i in range(len(nums)):
            if used[i]:       # 이미 사용한 원소는 건너뛰기
                continue

            used[i] = True    # 원소 사용 표시
            path.append(nums[i])

            backtrack(path)   # 다음 원소 선택으로 진행

            path.pop()        # 되돌림
            used[i] = False   # 사용 표시 해제

    backtrack([])
    return result


# 실행 예시
nums = [1, 2, 3]
print(permutations(nums, 2))

[[1, 2], [1, 3], [2, 1], [2, 3], [3, 1], [3, 2]]

              []
          /    |    \
        [1]   [2]   [3]
        / \   / \   / \
     [1,2][1,3] [2,1][2,3] [3,1][3,2]

def permutations_unique(nums):
    """중복 원소가 있는 경우의 순열 (중복 제거)"""
    result = []
    nums.sort()  # 정렬이 핵심: 같은 값을 인접하게 모은다
    used = [False] * len(nums)

    def backtrack(path):
        if len(path) == len(nums):
            result.append(path[:])
            return

        for i in range(len(nums)):
            if used[i]:
                continue
            # 핵심 가지치기: 같은 값인데 이전 것을 아직 안 썼으면 건너뛰기
            if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
                continue

            used[i] = True
            path.append(nums[i])
            backtrack(path)
            path.pop()
            used[i] = False

    backtrack([])
    return result


# 실행 예시
print(permutations_unique([1, 1, 2]))

[[1, 1, 2], [1, 2, 1], [2, 1, 1]]

def combinations(nums, r):
    """n개의 원소에서 r개를 뽑는 조합 생성"""
    result = []

    def backtrack(start, path):
        # 기저 조건: r개를 모두 선택
        if len(path) == r:
            result.append(path[:])
            return

        # start부터 탐색하여 중복 선택 방지 및 순서 강제
        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i + 1, path)  # i+1부터 탐색 (자기 자신 제외)
            path.pop()

    backtrack(0, [])
    return result


# 실행 예시
nums = [1, 2, 3, 4]
print(combinations(nums, 2))

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

def combinations_optimized(nums, r):
    """가지치기가 적용된 조합 생성"""
    result = []
    n = len(nums)

    def backtrack(start, path):
        if len(path) == r:
            result.append(path[:])
            return

        # 가지치기: 남은 원소 수가 부족하면 탐색 중단
        # 필요한 원소 수: r - len(path)
        # 사용 가능한 원소 수: n - i
        for i in range(start, n - (r - len(path)) + 1):
            path.append(nums[i])
            backtrack(i + 1, path)
            path.pop()

    backtrack(0, [])
    return result

def subsets(nums):
    """모든 부분집합 생성"""
    result = []

    def backtrack(start, path):
        # 매 단계가 유효한 부분집합이므로 바로 결과에 추가
        result.append(path[:])

        for i in range(start, len(nums)):
            path.append(nums[i])       # 원소 포함
            backtrack(i + 1, path)      # 다음 원소 결정
            path.pop()                  # 원소 제외 (되돌림)

    backtrack(0, [])
    return result


# 실행 예시
print(subsets([1, 2, 3]))

[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]

backtrack(0, [])          → 결과: []
  backtrack(1, [1])       → 결과: [1]
    backtrack(2, [1,2])   → 결과: [1,2]
      backtrack(3, [1,2,3]) → 결과: [1,2,3]
    backtrack(3, [1,3])   → 결과: [1,3]
  backtrack(2, [2])       → 결과: [2]
    backtrack(3, [2,3])   → 결과: [2,3]
  backtrack(3, [3])       → 결과: [3]

def solve_n_queens(n):
    """N-Queen 문제의 모든 해를 구한다"""
    results = []

    # 충돌 검사용 집합 (O(1) 조회)
    cols = set()       # 사용 중인 열
    diag1 = set()      # 좌상→우하 대각선 (row - col)
    diag2 = set()      # 우상→좌하 대각선 (row + col)

    board = [['.' for _ in range(n)] for _ in range(n)]

    def backtrack(row):
        # 기저 조건: 모든 행에 퀸을 배치 완료
        if row == n:
            # 보드 상태를 문자열로 변환하여 저장
            results.append([''.join(r) for r in board])
            return

        for col in range(n):
            # 가지치기: 열 또는 대각선 충돌 시 건너뛰기
            if col in cols or (row - col) in diag1 or (row + col) in diag2:
                continue

            # 퀸 배치
            cols.add(col)
            diag1.add(row - col)
            diag2.add(row + col)
            board[row][col] = 'Q'

            backtrack(row + 1)  # 다음 행으로 진행

            # 되돌림
            cols.remove(col)
            diag1.remove(row - col)
            diag2.remove(row + col)
            board[row][col] = '.'

    backtrack(0)
    return results


# 실행 예시: 4-Queen
solutions = solve_n_queens(4)
for i, sol in enumerate(solutions):
    print(f"해 {i + 1}:")
    for row in sol:
        print(f"  {row}")
    print()

print(f"총 {len(solutions)}개의 해")

해 1:
  .Q..
  ...Q
  Q...
  ..Q.

해 2:
  ..Q.
  Q...
  ...Q
  .Q..

총 2개의 해

row 0: col=0에 Q 배치 → [Q, -, -, -]
  row 1: col=0 (열 충돌) → skip
         col=1 (대각선 충돌: 0-0=0, 1-1=0) → skip
         col=2에 Q 배치 → [Q, -, Q, -]  (오류: 대각선!)
         col=2 (대각선 충돌: 0+0=0, 1+2=3, OK?) → ...

실제로는 row 0, col 0부터 시작해:
  row 1에서 col=2,3만 가능 → col=2 시도
    row 2에서 모든 열 충돌 → 백트래킹!
  row 1에서 col=3 시도
    row 2에서 col=1만 가능
      row 3에서 모든 열 충돌 → 백트래킹!

row 0: col=1에 Q 배치
  row 1: col=3에 Q 배치
    row 2: col=0에 Q 배치
      row 3: col=2에 Q 배치 → 해 발견!

def combination_sum(candidates, target):
    """합이 target이 되는 모든 조합을 구한다 (중복 사용 가능)"""
    result = []
    candidates.sort()  # 정렬하면 가지치기에 유리

    def backtrack(start, path, remaining):
        # 기저 조건: 목표 합에 도달
        if remaining == 0:
            result.append(path[:])
            return

        for i in range(start, len(candidates)):
            # 가지치기: 남은 값보다 큰 후보는 탐색 불필요
            if candidates[i] > remaining:
                break  # 정렬되어 있으므로 이후 값도 모두 초과

            path.append(candidates[i])
            # 같은 숫자 재사용 가능하므로 i (i+1이 아님)
            backtrack(i, path, remaining - candidates[i])
            path.pop()

    backtrack(0, [], target)
    return result


# 실행 예시
print(combination_sum([2, 3, 6, 7], 7))

[[2, 2, 3], [7]]

def combination_sum2(candidates, target):
    """합이 target이 되는 조합 (각 숫자 1회만 사용, 중복 후보 허용)"""
    result = []
    candidates.sort()

    def backtrack(start, path, remaining):
        if remaining == 0:
            result.append(path[:])
            return

        for i in range(start, len(candidates)):
            if candidates[i] > remaining:
                break
            # 같은 레벨에서 중복 값 건너뛰기
            if i > start and candidates[i] == candidates[i - 1]:
                continue

            path.append(candidates[i])
            backtrack(i + 1, path, remaining - candidates[i])  # i+1: 재사용 불가
            path.pop()

    backtrack(0, [], target)
    return result


# 실행 예시
print(combination_sum2([10, 1, 2, 7, 6, 1, 5], 8))

[[1, 1, 6], [1, 2, 5], [1, 7], [2, 6]]

def solve_sudoku(board):
    """스도쿠를 백트래킹으로 풀기"""

    # 각 행, 열, 박스에서 사용 중인 숫자를 집합으로 관리
    rows = [set() for _ in range(9)]
    cols = [set() for _ in range(9)]
    boxes = [set() for _ in range(9)]  # 박스 인덱스: (row//3)*3 + col//3

    empty = []  # 빈 칸 좌표 목록

    # 초기 상태 설정
    for r in range(9):
        for c in range(9):
            if board[r][c] != '.':
                num = int(board[r][c])
                rows[r].add(num)
                cols[c].add(num)
                boxes[(r // 3) * 3 + c // 3].add(num)
            else:
                empty.append((r, c))

    def backtrack(idx):
        # 기저 조건: 모든 빈 칸을 채웠음
        if idx == len(empty):
            return True

        r, c = empty[idx]
        box_id = (r // 3) * 3 + c // 3

        for num in range(1, 10):
            # 가지치기: 행, 열, 박스 충돌 검사
            if num in rows[r] or num in cols[c] or num in boxes[box_id]:
                continue

            # 숫자 배치
            board[r][c] = str(num)
            rows[r].add(num)
            cols[c].add(num)
            boxes[box_id].add(num)

            if backtrack(idx + 1):  # 다음 빈 칸으로
                return True

            # 되돌림
            board[r][c] = '.'
            rows[r].remove(num)
            cols[c].remove(num)
            boxes[box_id].remove(num)

        return False  # 1~9 모두 불가능 → 백트래킹

    backtrack(0)
    return board


# 실행 예시
board = [
    ['5','3','.','.','7','.','.','.','.'],
    ['6','.','.','1','9','5','.','.','.'],
    ['.','9','8','.','.','.','.','6','.'],
    ['8','.','.','.','6','.','.','.','3'],
    ['4','.','.','8','.','3','.','.','1'],
    ['7','.','.','.','2','.','.','.','6'],
    ['.','6','.','.','.','.','2','8','.'],
    ['.','.','.','4','1','9','.','.','5'],
    ['.','.','.','.','8','.','.','7','9']
]

solve_sudoku(board)
for row in board:
    print(' '.join(row))

5 3 4 6 7 8 9 1 2
6 7 2 1 9 5 3 4 8
1 9 8 3 4 2 5 6 7
8 5 9 7 6 1 4 2 3
4 2 6 8 5 3 7 9 1
7 1 3 9 2 4 8 5 6
9 6 1 5 3 7 2 8 4
2 8 7 4 1 9 6 3 5
3 4 5 2 8 6 1 7 9

# 잘못된 코드: 모든 결과가 같은 리스트를 참조
result.append(path)       # path가 변경되면 result도 변경됨

# 올바른 코드: 깊은 복사로 현재 상태 저장
result.append(path[:])    # 슬라이싱으로 복사
result.append(list(path)) # 또는 list()로 복사

# 잘못된 코드: 상태 복원을 잊음
path.append(nums[i])
backtrack(path)
# path.pop() 누락!

# 올바른 코드
path.append(nums[i])
backtrack(path)
path.pop()  # 반드시 되돌려야 함

# 잘못된 코드: 순열이 생성됨
backtrack(0, path)         # 매번 처음부터 탐색

# 올바른 코드: 조합이 생성됨
backtrack(i + 1, path)     # 현재 이후부터 탐색

# 비효율적: 깊이 들어간 후 확인
path.append(nums[i])
if not is_valid(path):
    path.pop()
    continue
backtrack(path)
path.pop()

# 효율적: 선택 전에 확인
if not is_valid_choice(nums[i]):  # 선택 전 검증
    continue
path.append(nums[i])
backtrack(path)
path.pop()

def n_queens_bitmask(n):
    """비트마스크를 활용한 N-Queen 카운팅"""
    count = 0

    def backtrack(row, cols, diag1, diag2):
        nonlocal count
        if row == n:
            count += 1
            return

        # 사용 가능한 열을 비트 연산으로 계산
        available = ((1 << n) - 1) & ~(cols | diag1 | diag2)

        while available:
            # 가장 오른쪽 1비트 추출
            pos = available & (-available)
            available ^= pos

            backtrack(
                row + 1,
                cols | pos,              # 열 마킹
                (diag1 | pos) << 1,      # 좌상→우하 대각선
                (diag2 | pos) >> 1       # 우상→좌하 대각선
            )

    backtrack(0, 0, 0, 0)
    return count


print(f"8-Queen 해의 수: {n_queens_bitmask(8)}")

8-Queen 해의 수: 92

from itertools import permutations, combinations, product

# 순열
list(permutations([1, 2, 3], 2))    # [(1,2), (1,3), (2,1), (2,3), (3,1), (3,2)]

# 조합
list(combinations([1, 2, 3, 4], 2)) # [(1,2), (1,3), (1,4), (2,3), (2,4), (3,4)]

# 중복 순열 (데카르트 곱)
list(product([0, 1], repeat=3))     # 길이 3의 모든 이진 수열