백준 1182. 부분수열의 합

https://www.acmicpc.net/problem/1182

1182번: 부분수열의 합

from sys import stdin
input = stdin.readline

n, s = map(int, input().split())
arr = list(map(int, input().split()))
cnt = 0

def dfs(idx, tmp):
    global cnt
    if idx >= n:    # 현재 인덱스가 정수의 개수보다 크면 리턴
        return
    tmp += arr[idx] # 수열에 현재 인덱스의 정수를 더함
    if tmp == s:    # 그 수가 s라면 카운트
        cnt += 1
    dfs(idx+1, tmp) # 현재 인덱스의 정수를 더한 것
    dfs(idx+1, tmp-arr[idx]) # 현재 인덱스의 정수를 더하지 않은 것

    # 이렇게 두 갈래로 쭉쭉 가지치기를 해가서 모든 부분집합의 합을 보는 것!

dfs(0, 0)
print(cnt)

이해를 하지 못한 풀이

N, S = map(int, input().split())
num = list(map(int, input().split()))
cnt = 0
ans = []

def solve(start):
    global cnt
    if sum(ans) == S and len(ans) > 0:  # 목표값 찾았고, 적어도 하나 이상의 원소가 있으면
        cnt += 1
    for i in range(start, N):  # start부터 n-1까지의 수를 리스트에 추가
        ans.append(num[i])
        solve(i+1)
        ans.pop()

solve(0)
print(cnt)