[프로그래머스] (Python) - 타겟 넘버

https://programmers.co.kr/learn/courses/30/lessons/43165

코딩테스트 연습 - 타겟 넘버

 

문제 유형 : DFS / BFS

 

풀이 

dfs(idx, 누적값):
	if idx == numbers의 개수  # 재귀 종료조건 : 모든 요소를 더하거나 뺐다면 종료
		if 누적값 == target:   # 모든요소를 더하거나 뺐는데, 누적값이 target과 일치하면 answer += 1
			answer += 1
		return

	# 아직 종료전이라면
	dfs(idx, 누적값 + numbers[idx]) # 다음 숫자를 더하는 경로
	dfs(idx, 누적값 - numbers[idx])  # 다음 숫자를 빼는 경로

 

answer = 0

def dfs(max_len, cnt, result, target, numbers):
    
    if cnt == max_len:
        if result == target:
            global answer
            answer += 1
        return
    dfs(max_len, cnt + 1, result + numbers[cnt] ,target, numbers)
    dfs(max_len, cnt + 1, result - numbers[cnt] ,target, numbers)    
    


def solution(numbers, target):
    global answer
    max_len = len(numbers)
    dfs(max_len, 0, 0, target, numbers)
    return answer