[Programmers] Level 2. 타겟 넘버

🔗 Problem Link

프로그래머스

---

❔Thinking

• 음이 아닌 정수를 주어진 개수만큼 더하거나 빼서 target을 만든다
• 더하거나 빼는 경우는 순서에 상관이 없다.

---

💻Solution

def solution(numbers, target):
    answer = 0
    def make_target(result, cnt):
        nonlocal answer
        if cnt == len(numbers):
            if result == target:
                answer += 1
            return
        make_target(result+numbers[cnt], cnt+1)
        make_target(result-numbers[cnt], cnt+1)
    make_target(0, 0)
    return answer

---

🗝️keypoint

1. 처음 등장하는 정수 또한 -과 + 모두 가능하다는 사실에 유의한다.
2. BFS, DFS로 풀이하고, 주어진 정수를 모두 사용한 경우를 종료 조건으로 한다.