백트래킹의 기본 구조

def 재귀함수(n):
	if 정답이면 :
		출력 or 저장
	else : 정답이 아니면 :
		for 모든 자식 노드에 대해서:
			if 정답에 유망하다면(답의 가능성이 있으면) :
				자식노드로이동
				재귀함수(n+1)
				부모노드로 이동

 

 

혹은 유망 조건을 따로 함수로 빼줘서 구현한다.

def 백트래킹(n):
	if 정답이면 :
		출력 or 저장
	else :
		for 모든 자식 노드에 대해 :
			if 유망한지확인(m) :
				자식노드로 이동
				백트래킹(n+1)
				부모노드로 이동

def 유망한지확인(m):
	if 조건에 안맞으면 :
		return False
	return True

 

 

---

# 1182번: 부분수열의 합

n, s = map(int, input().split())
arr = sorted(list(map(int, input().split())))

# 부분수열의 합이 S가 되는 경우의 수
answer = 0

result = []

def backTracking(num):
    if len(result) > 0 and sum(result) == s:
        global answer
        answer += 1
        # return
    
    for i in range(num, n):
        result.append(arr[i])
        backTracking(i+1)
        result.pop()


backTracking(0)
print(answer)

 

그리고 위 코드의 경우처럼 꼭 return을 하지 않고, 답을 구할 수도 있다.

문제마다 다르게 구현할 수 있다.