[프로그래머스]level2-타겟 넘버-Python[파이썬]

문제링크

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

문제설명

알고리즘

numbers = [4, 1, 2, 1]이고 target은 4라면
target값인 4를 만드려면 아래 그래프처럼 가지 치기를 할 수 있다.
--> 3에 1을 더하기 or 5에 1을 빼기
--> 4를 만드는 경우의 수 == 3을 만드는 경우의 수 + 5를 만드는 경우의 수
따라서 3과 5를 새로운 target으로 지정하고 numbers의 마지막 원소(1)을 제외한 리스트 [4, 1, 2]를 새로운 numbers로 지정하여 solution함수를 재귀호출한다.

이때 파란색으로 색칠한 값은 numbers리스트들 값들을 역순(1->2->1->4)으로 나타낸 것이다.

이렇게 solution함수를 재귀호출하면 다음과 같이 계속 가지 치기를 할 수 있고
solution함수를 호출할 때 numbers 길이는 1이 된다.

이때 numbers값이 target의 절댓값과 같다면 target을 만들 수 있는 것이므로 1을 return한다. 만일 둘이 다르다면 target을 만들 수 없는 것이므로 0을 return.
이 값들을 모두 더하면 최종 target값인 4를 만들는 총 가짓수가 된다.

코드

def solution(numbers, target):
    print(numbers, target)
    if len(numbers) == 1:
        if numbers[0] == abs(target):
            print('가능')
            cnt = 1
        else:
            cnt = 0
        return cnt
    return solution(numbers[:-1], target - numbers[-1]) + solution(numbers[:-1], target + numbers[-1])