[프로그래머스] - 타겟넘버

*제출코드

all = [] #주어진 숫자를 모두 조합(더하기,빼기)해서 나올수 있는 값을 기록 
sum = 0 #파라미터로 넘기지 않고 두 함수에서 쓰기위해 전역으로 선언
arr = [] # "

def dfs(index):
    global all , arr, sum
    
    sum += arr[index] #이전까지 기록된 sum에 해당 인덱스의 값을 더한다
    if index == len(arr)-1: #맨마지막 원소까지 더한 것이라면
        all.append(sum) #값을 기록한다
    else:
        dfs(index+1) #아니라면 다음 인덱스로 이동한다
    sum -= arr[index] #sum에 더했던 인덱스 값을 원상복귀 시켜준다
    
    sum -= arr[index] #이전까지 기록된 sum에서 해당 인덱스의 값을 뺀다
    if index == len(arr)-1:
        all.append(sum)
    else:
        dfs(index+1)
    sum += arr[index] #sum에서 뺐던 인덱스 값을 원상복귀 시켜준다

    
def solution(numbers, target):
    global arr
    arr= numbers
    dfs(0)
    answer = all.count(target) #나온 값 중에서 target number와 일치하는 값의 개수를 센다.
        
    return answer

 

*review

0. 가능한 모든 조합을 구해야해서 dfs로 풀었다.

 

1. 처음 시도는 dfs로 풀 방법을 찾다보니 그래프 구조를 dictionary로 짰던 것이 기억나서 딕셔너리 구조로 풀려 했다.

 

예를들어 [2,3,5] 의 numbers가 입력되었을 때 

2라는 값에서 더하거나 뺄 수 있는 것은 3이라는 값이고,

3이라는 값에서 덧셈뺄셈을 할 수 있는것은 5라는 값이라고 생각해서

방향 그래프 {2:[3],3:[5],5:[]} 로 구조를 짜고 코드를 짰다.

 

그런데 테스트 케이스 [1,1,1,1]에는 적용되지 않는 구조였다.

파이썬 dictionary는 중복된 키 값을 허용하지 않기 때문이다.

 

2. 생각해보니 굳이 dictionary로 하지 않고 list로 해도 됐다. 현재 인덱스에서 갈 수 있는 곳은 다음 인덱스 뿐이기 때문이다.

 

마지막 인덱스에 도착했을 때만 최종 sum값을 기록해주고, 마지막 인덱스가 아니라면 다음인덱스로 갈 수 있도록 재귀적으로 함수를 짜주었다.