[알고리즘] Backtracking

🔱 백트래킹

- 여러 가지 선택들 중 한 가지를 선택
- 선택이 이루어지면 새로운 선택지들의 집합이 생성
- 이런 선택을 반복하면서 최종 상태(목표)에 도달

1. 전체 경우의 수 고려
2. 가능성 없는 경우의 수 제거 (가지치기)

---

백트래킹과 DFS의 차이

• DFS를 하기에는 경우의 수가 너무 많은 문제에 있어서 백트래킹 활용
• 백트래킹은 불필요한 경로를 조기 차단, 시도의 횟수를 줄임

  백트래킹을 적용하면 일반적으로 경우의 수가 줄어들지만 최악의 경우 여전히 지수함수 시간을 요구 (DFS와 동일)

※ 많은 경우의 수를 제거할 수 있는가?

---

집합의 부분집합을 구하는 백트래킹 알고리즘

# {1, 2, 3} 집합에서 3개의 숫자를 선택하는 기본 예제
# 조건) 이미 사용한 숫자는 사용하지 않도록 

arr = [i for i in range(1, 4)]
path = [0] * 3

def backtracking(cnt):
	# 기저 조건 : 숫자 3개를 골랐을 때 종료
    if cnt == 3:
    	print(*path)
    	return
    
    for num in arr:
    	# 가지치기 - 중복된 숫자 제거
        if num in path:
        	continue
    	# 들어가기 전 로직
        path[cnt] = num
    # 다음 재귀 함수 호출
    backtracking(cnt + 1)
    # 돌아와서 할 로직 : 초기화
    path[cnt] = 0
    

+ {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} 의 부분집합 중 원소의 합이 10인 부분집합 모두 구하기 (연습)

• 추후, 구현한 코드 작성!!