프로그래머스 | 타겟넘버 문제풀이

문제 접근 방법

+, - 를 이용해서 만들 수 있는 모든 경우를 확인하고, 

이 경우 중 타겟넘버와 값이 같다면 개수를 추가해주는 방식으로 풀었음.

 

모든 경우를 확인하는 함수는 재귀함수를 이용해서 구현.

 

처리 방법

1. 재귀함수를 통해 현재 항의 위치를 확인

      1.1. 끝까지 계산했고 수식의 결과가 target 과 같으면 수를 1 추가.

      1.2. 끝까지 계산했고 target과 같지 않은 경우, 0 반환

      1.3. 아직 계산 중일 경우

           1.3.1. 지금까지 구한 총합(total)에 현재 해당하는 수를 각각 더하고 빼주면서 함수를 호출한다.

2. dfs(..., index= 0,total= 0) 을 호출하여 첫번째 항에서부터 계산을 시작한다.

코드

def dfs(nums,n,target,index, total):
    if index == n  and total == target:
        return 1
    elif index >= n:
        return 0

    return dfs(nums,n,target,index + 1, total - nums[index]) + dfs(nums,n,target,index + 1, total + nums[index])


def solution(numbers, target):
    n = len(numbers)
    numbers.append(0)

    return dfs(numbers,n,target,0, 0)