[프로그래머스] 타겟 넘버

---

1. 문제

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

프로그래머스

 

 

2. 알고리즘 

1. 덧셈 뺄셈 모든 연산을 확인해본다

2. dfs로 전부 해보는게 솔루션 

3. 종료 조건은 현재값이 target 값이며 모든 numbers를 idx를 확인하고 마지막 len(numbers)에 왔을때 최종 결과 값이 나오므로 종료 (여기서 실수 마지막 배열값에 도달하기 전에 중지 하면 값이 안나옴)

 

---

3. 코드 

answer = 0
def solution(numbers, target):
    
    def dfs(idx, cur):
        global answer
        if cur == target and idx == len(numbers): #마지막 연산까지 진행 후 target number에 도달 한 경우 정답 카운트
            answer += 1 
            return
        if idx >= len(numbers): return #인덱스 벗어남 방지 
        
        dfs(idx+1, cur+numbers[idx]) #덧셈연산 
        dfs(idx+1, cur-numbers[idx]) #뺄셈연산
    
    dfs(0,0)
    return answer