타켓넘버→ DFS(깊이우선탐색)★★+요소 더하기, 요소 빼기+ 재귀함수

나의 틀린 풀이

def solution(numbers, target):
    return DFS(0, 0, target, 0)
   
   

def DFS(L, sum, target, cnt):
  if L ==len(numbers):
      if sum == target:
           cnt+=1
           return cnt
  else:
     DFS(L+1, sum-numbers[L], target, cnt)
     DFS(L+1, sum+numbers[L], target, cnt)

 

numbers = [4, 1, 2, 1]
target = 4


print(solution(numbers, target))

 

 

 

 

성공한 나의 풀이 

def solution(numbers, target):
    def DFS(L, sum, target, cnt):
        if L ==len(numbers):
            if sum == target:
                cnt+=1
        else:
            cnt = DFS(L+1, sum-numbers[L], target, cnt)
            cnt = DFS(L+1, sum+numbers[L], target, cnt)
        return cnt

    return DFS(0, 0, target, 0) #return으로 함수를 종료하는 것이 아니라 다른 함수를 호출한다.
   

numbers = [4, 1, 2, 1]
target = 4

print(solution(numbers, target))

 

 

▶ cnt의 값을 계속 갱신시키지 않고, 반영된 값을 끌고 가려면,

     DFS의 리턴값으로 받아줘야 끌고 다닐수 있다. 

 
▶ 그리고 마지막 줄에서 최종값으로 DFS에서 return을 해줘야 계속 DFS탐색을 하면서 cnt값을 끌고 간다.  

 

▶ target같은 경우 항상 같은 값이어야 하므로 별도의 조치를 취하지 않는다. 

 

▶ 다만, sum의 경우 numbers의 요소를 더해서 값을 누적시켜야 되므로

    sum-numbers[L] 또는 sum+numbers[L]를 해서 값을 누적시켜 나간다. 

 

 

▶ 재귀 타고 들어가서 젤 안쪽 함수에서 리턴하더라도

     바로 바깥쪽 함수가 받는거지 젤 바깥 쪽 함수가 받는게 아니다.

 

"구슬을 나누는 경우의 수"를 보면 

solution()함수의 리턴값을 result로 받아주고,

마지막 줄에서 return result하고 있다. 

https://copro505.tistory.com/entry/%EA%B5%AC%EC%8A%AC%EC%9D%84-%EB%82%98%EB%88%84%EB%8A%94-%EA%B2%BD%EC%9A%B0%EC%9D%98-%EC%88%98

구슬을 나누는 경우의 수→순수(?) 조합 계산★★

 

 

 

 

다른 사람의 정석 풀이

cnt = 0
def DFS(idx, numbers, target, value):
    global cnt
    N = len(numbers)
    if(idx== N and target == value):
        cnt += 1
        return
    if(idx == N):
        return

    DFS(idx+1,numbers,target,value+numbers[idx])
    DFS(idx+1,numbers,target,value-numbers[idx])
    
    
def solution(numbers, target):
    global cnt
    DFS(0,numbers,target,0)
    return cnt

 

cnt를 global로 설정하면, 굳이 cnt를 매개변수로 하여 끌고 다닐 필요가 없다.