프로그래머스_타겟넘버

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

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

 

◎ Code

def solution(numbers, target):
    answer = 0

    def back(result, point) :
        if point == len(numbers) :
            if result == target :
                nonlocal answer 
                answer += 1
            return 

        back(result + numbers[point], point + 1)
        back(result - numbers[point], point + 1)
    back(0, 0)

    return answer

print(solution([1,1], -2))
print(solution([2,3,5,7,9], 2))

 

◎ Code 설명

- DFS (Depth-First-Search)

- numbers의 point(인덱스) 값마다 덧셈,뺄셈으로 누적한다

- 초기에 누적값 0,  point(인덱스) 0을 호출한다

   -> 초기누적값 0에 numbers의 0번째 값을 덧셈 / 뺄셈 (point 증가 = 인덱스 증가)

- 입력값 numbers배열의 point번째 숫자의 덧셈, 뺄셈을 누적하며 DFS 실행.

- point가 len(numbers)와 같을 때가 모든 숫자를 사용했을 경우 이므로

  그때 누적된 값이 target과 같을 때는 answer + 1 and return, 아니면 그냥 return