문제

<예제>
[1, 1, 1, 1, 1], 3  -> 5
[4, 1, 2, 1], 4  -> 2

+4 +1 -2 +1 = 4
+4 -1 +2 -1 = 4    -> 4가 나오는 경우, 2가지

Q. 왜 bfs, dfs 문제일까?
      3 ...
   2
1     1
   0	
   	  -1   -> 이런식으로 탐색해야해서
      

풀이

쉬운 풀이

# 전체적으로 구한 뒤 target 넘버가 나오는 경우의 수만 count하면되는데 
  잘못생각해서 엉켜버려 시간을 날린 뒤 해답을 찾아보았다.
  
1. 처음 값 sup= [0], 연산값이 들어갈 result = []를 만든다.
2. sup 값과 numbers의 값들을 더하거나 빼서 result에 삽입
3. result 값과 numbers의 값들을 연산한다.  
4. 2번부터 (반복)

def solution(numbers, target):
    sup = [0]                       # 처음엔 0으로

    for i in numbers:
        result = []
        for j in sup:
            result.append(j + i)	# 0 + 4 = 4
            result.append(j - i)	# 0 - 4 = -4
        sup = result                # 구한 값으로 다시 계산하기위해

    return sup.count(target)


print(solution([4, 1, 2, 1], 2))

# result
# [4, -4]
# [5, 3, -3, -5]
# [7, 3, 5, 1, -1, -5, -3, -7]
# [8, 6, 4, 2, 6, 4, 2, 0, 0, -2, -4, -6, -2, -4, -6, -8]  -> 4의 개수, 2개

재귀를 활용한 풀이

answer = 0
def DFS(idx, numbers, target, value):
    global answer
    N = len(numbers)
    if idx == N and target == value:    # 4이고, value = 4 -> +1
        answer += 1
        return
    if idx == N:                        # 4일 때 멈춤
        return

    DFS(idx+1, numbers, target, value+numbers[idx])
    DFS(idx+1, numbers, target, value-numbers[idx])

def solution(numbers, target):
    global answer
    DFS(0,numbers,target,0)
    return answer

print(solution([4, 1, 2, 1], 4))    -> 2


DFS(1, , ,0 + 4)
DFS(1, , ,0 - 4)

DFS(2, , ,4 + 1)
DFS(2, , ,4 - 1)
DFS(2, , ,-4 + 1)
DFS(2, , ,-4 - 1)

DFS(3, , ,5 + 2)
DFS(3, , ,5 - 2)
...


DFS(4, , ,7 + 1)	# if문 들어감
DFS(4, , ,7 - 1)
DFS(4, , ,3 + 1)  	+1
DFS(4, , ,3 - 1)
...

모르겠는 풀이

def solution(numbers, target):
    print(numbers)
    print(target)
    if not numbers and target == 0 :
        return 1
    elif not numbers:
        return 0
    else:
        return solution(numbers[1:], target-numbers[0]) +
        	   solution(numbers[1:], target+numbers[0])

타겟 넘버