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

Problem

더하기와 빼기를 이용해 배열중 target을 만들 수 있는 모든 경우의 수 구하기

Solution

dfs를 2번 호출하여 구현

코드설명

1)두 경우의 dfs 호출을 통해 탐색
dfs(sum+numbers[depth],depth+1,numbers,target)
dfs(sum-numbers[depth],depth+1,numbers,target)
2) depth의 깊이가 배열만큼 dfs돌고, 그 합이 target이라면 리턴

Python Code

cnt=0
def dfs(sum,depth,numbers,target):
    global cnt
    if depth==len(numbers):
        if sum==target:
            cnt+=1
            return
    else:
        dfs(sum+numbers[depth],depth+1,numbers,target)
        dfs(sum-numbers[depth],depth+1,numbers,target)
def solution(numbers, target):
    dfs(0,0,numbers,target)
    return cnt