백트래킹[Back tracking]

1. 백트래킹 = 모든 경우의 수를 다 탐색하는 알고리즘 -> 조합이나 그래프와 같이 모든 경우의 수를 탐색해야 하는 문제에 적합

2. 어떻게 모든 경우의 수를 탐색하는가?

주어진 조건과 제약 사항을 만족하는 해를 찾는 과정에서, 현재 상태에서 조건을 만족하지 않으면 이전 단계로 돌아가서(Back) 다른 선택지를 시도

3. 예시 조합 문제. 3C2

def backtrack(nums, path, M, result):
    if M == 0:  # M개의 수를 모두 선택한 경우
        result.append(path[:])  # 결과에 추가
        return
    
    for i in range(len(nums)):
        path.append(nums[i])  # 수 선택
        backtrack(nums[i+1:], path, M-1, result)  # 다음 수로 재귀 호출
        path.pop()  # 선택한 수 제거

N = 3  # 1부터 N까지의 수
M = 2  # 2개의 수를 선택

nums = list(range(1, N+1))
path = []
result = []

backtrack(nums, path, M, result)

print(result)

1. 1 선택 (1)

2. 2 선택 (1,2)

3. 2(M)개 선택 -> return -> result 에 (1,2) 추가

4. pop -> (1)

5. 3선택 

6. 2(M)개 선택 -> return -> result 에 (1,3) 추가

7. pop -> (1)

8. pop -> ()

9. 2선택 (2)

10. 3선택 

11.  2(M)개 선택 -> return -> result 에 (2,3) 추가

12. pop -> (2)

13. pop -> ()

14. 종료