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

DFS 풀이

cnt = 0
def solution(numbers, target):
    cur_sum = 0
    idx = 0
    dfs(idx, cur_sum, numbers, target)
    return cnt

def dfs(idx, cur_sum, numbers, target):
    global cnt
    if idx == len(numbers):
        if cur_sum == target:
            cnt += 1
        return
    dfs(idx + 1, cur_sum + numbers[idx], numbers, target)
    dfs(idx + 1, cur_sum - numbers[idx], numbers, target)

• 평소에 DFS/BFS 문제를 그래프, 길찾기 종류의 유형으로만 접하다 보니
  DFS 유형이라고 써있는 힌트가 오히려 더 혼란을 가져왔던거 같다.

과연 이 문제가 DFS 인가?

• 찾아보니 DFS 는 본래 다음 경로로 이동하기 전에 각 경로를 완전히 탐색하는 것.

• 이 문제에서 각 경로는 목표 합계에 도달하기 위해 주어진 숫자를 더하고 빼는 고유한 조합을 나타내기에 DFS 로 볼 수 있다.

재귀가 진행되는 과정이 궁금해

numbers = [1, 1, 1, 1, 1]
target = 3
cnt = 0

def solution(numbers, target):
    cur_sum = 0
    idx = 0
    dfs(idx, cur_sum, numbers, target,"")
    return cnt


def dfs(idx, cur_sum, numbers, target,state):
    global cnt
    if idx == len(numbers):
        if cur_sum == target:
            cnt += 1
        print(state)
        return
    dfs(idx + 1, cur_sum + numbers[idx], numbers, target, state + "+")
    dfs(idx + 1, cur_sum - numbers[idx], numbers, target, state+ "-")


print(solution(numbers, target))

+++++
++++-
+++-+
+++--
++-++
++-+-
++--+
++---
+-+++
+-++-
+-+-+
+-+--
+--++
+--+-
+---+
+----
-++++
-+++-
-++-+
-++--
-+-++
-+-+-
-+--+
-+---
--+++
--++-
--+-+
--+--
---++
---+-
----+
-----
5

• 재귀가 진행될때마다 바뀌는 부호를 출력해보았다.

---

다른 풀이는 없을까?

• 이 문제의 경우 숫자의 개수가 2~20개 이기 때문에 재귀가 가능하지만, 숫자가 커지게 되면 매우 비효율적이다.

• 메모리제이션을 활용하는 dp 로도 접근이 가능하다.

numbers = [1, 1, 1, 1, 1]
target = 3

def solution(numbers, target):
    total_sum = sum(numbers)
    offset = total_sum

    dp = [[0 for _ in range(2 * total_sum + 1)] for _ in range(len(numbers))]

    dp[0][numbers[0] + offset] = 1
    dp[0][-numbers[0] + offset] += 1 # 첫번째 숫자가 0인경우를 방지

    for i in range(1, len(numbers)):
        for j in range(2 * total_sum + 1):
            if dp[i - 1][j] != 0:
                dp[i][j + numbers[i]] += dp[i - 1][j]
                dp[i][j - numbers[i]] += dp[i - 1][j]

    return dp[len(numbers) - 1][target + offset]


print(solution(numbers, target))

• 사실 2차원 배열 DP 를 아직 접해본 경험이 없어서 이해하는데 많이 어려웠다.

키 포인트

• 첫 번째 차원은 '숫자' 배열의 각 인덱스를 나타내고,

• 두 번째 차원은 해당 인덱스에서 얻을 수 있는 가능한 합계를 나타냅니다.

• 두 번째 차원의 크기는 가능한 합계 범위(음수 합계에서 양수 합계까지)를 수용할 수 있을 만큼 커야 합니다.

• 합계가 음수일 수 있지만 배열 인덱스에 음수를 저장할 수 없음으로
  양수의 합계를 유지하기 위해 오프셋 'sum(numbers)' (경우의 수의 최고 합)을 사용!

• 첫번째 숫자가 0인경우를 방지하기 위해

 dp[0][-numbers[0] + offset] += 1

를 사용한다.