브루트포스) 1182.부분수열의 합

Carnival7 2022. 6. 7. 18:19

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

1182번: 부분수열의 합

첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.

www.acmicpc.net

n,s = map(int,input().split())
nums=list(map(int,input().split()))

answer=0

# solution 1
def dfs(index,arr,m):
    global answer
    # 정답을 찾은 경우
    if len(arr) == m:
        if sum(arr) == s:
            answer+=1
        return
    # 불가능한 경우
    if index==n:
        return

    dfs(index+1,arr+[nums[index]],m)
    dfs(index + 1, arr, m)

for i in range(1,n+1):
    dfs(0,[],i)

print(answer)

# solution 2
answer=0
def go(index,m):
    global answer
    if index==n:
        if m==s:
            answer+=1
        return
    go(index+1,m+nums[index])
    go(index+1,m)

go(0,0)
if s==0:
    answer-=1
print(answer)