target으로 계산되는 경우의 수 구하기: DFS

모든 경우의 수에서 target의 개수를 구하는 문제

사용하는 경우: 모든 노드를 방문 하고자 하는 경우이므로 DFS 계산

# 타겟 넘버를 만드는 방법의 수 -> DFS (모든 경우 탐색)
answer = 0
def DFS(numbers, target, idx=0, value=0):
    global answer
    N = len(numbers)
    
    # idx가 마지막이고 value가 target과 같을 때는 answer
    if(idx == N and target == value):
        answer += 1
        return
    elif(idx == N):   # idx가 마지막이기만 하면 non answer
        return

    DFS(numbers,target,idx+1,value+numbers[idx])	# idx번째 수를 더해준 경우로 재귀
    DFS(numbers,target,idx+1,value-numbers[idx])	# idx번째 수를 빼준 경우로 재귀
    
def solution(numbers, target):
    global answer
    
    DFS(numbers, target)
    
    return answer

 

 

 

BFS 코드

def solution(numbers, target):
    leaves = [0]  
    count = 0 

    for num in numbers:
        temp = list()
	
        for leaf in leaves:
            temp.append(leaf + num)    # 더하는 경우
            temp.append(leaf - num)    # 빼는 경우

        leaves = temp

    # 모든 경우의 수 계산 후 target과 같은지 확인 
    for leaf in leaves:
        if leaf == target: 
            count += 1

    return count