[SWEA/D3] 2817 부분 수열의 합 / 백트래킹

문제 바로가기

SW Expert Academy

나의 코드 및 설명 - 멀티 트리

• 현재 방문한 수열의 인덱스에 대해 v 리스트를 활용하여 방문 처리를 해주었고, 합의 개수를 셀 때 중복된 값을 세지 않도록 for문의 시작점을 dfs의 변수에 넘겨주었다. 

def dfs(count, temp_sum, start):
    global ans
    if temp_sum >= k:
        if temp_sum == k:
            ans += 1
        return
    if count == n:
        return
    
    for i in range(start, n):
        if v[i] == 0:
            v[i] = 1
            dfs(count + 1, temp_sum+num_list[i], i+1)
            v[i] = 0
    
t = int(input())
for test_case in range(1, t+1):
    n,k = map(int, input().split())
    num_list = list(map(int, input().split()))
    num_list.sort()
    ans = 0
    v = [0] * (n)
    dfs(0,0,0)
    print(ans)

다른 코드 및 설명 - 이진 트리

def dfs(index, temp_sum):
    global ans
    if temp_sum > k:
        return
    if temp_sum == k:
        ans += 1
        return
    if index == n:
        return
    dfs(index+1, temp_sum)
    dfs(index+1, temp_sum+num_list[index])


t = int(input())
for test_case in range(1, t+1):
    n,k = map(int, input().split())
    num_list = list(map(int, input().split()))
    num_list.sort()
    ans = 0
    v = [0] * (n)
    dfs(0, 0)
    print("#{} {}".format(test_case, ans))