99클럽 코테 스터디 8일차 TIL + 깊이/너비 우선 탐색(DFS/BFS) - 타겟 넘버

 

🔗 프로그래머스 - 타켓 넘버

재귀로 풀었다!!

각 숫자 사이에 + 또는 - 연산자를 넣어줘야 하는데

재귀로 돌면서 디시전 트리 도는 것 처럼 + , - 를 선택하고 마지막 숫자까지 갔을때 target과 같으면 count += 1를 해줘서 답을 얻었다.

def solution(numbers, target):
    def choose(idx, num_sum):
        if idx == len(numbers):
            if num_sum == target:
                return 1
            return 0
        return choose(idx + 1, num_sum + numbers[idx]) + choose(idx + 1, num_sum - numbers[idx])

    answer = choose(0, 0)
    return answer


print(solution([1, 1, 1, 1, 1], 3)) # 5
print(solution([4, 1, 2, 1], 4)) # 2