백준 1182 부분수열의 합

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

1182번: 부분수열의 합

 

풀이 1:

dfs로 모든 수열을 구한다음, 0이되는경우를 센다

n,s=map(int,input().split())
nums=[* map(int,input().split())]
visit=[False for _ in range(n)]
cnt=0
tmp=[]
def dfs(start=0):
    global cnt
    if tmp:
        if sum(tmp)==s:
            cnt+=1
    if len(tmp)==n:
        return
    for i in range(start,len(nums)):
        if not visit[i]:
            tmp.append(nums[i])
            dfs(i+1)
            tmp.pop()
            visit
dfs()
print(cnt)

풀이2:

각각의 원소를 포함/포함안하는 2가지 방향으로 뻗어나가는 dfs

n,s=map(int,input().split())
nums=[* map(int,input().split())]
cnt=0

def dfs(v=0,depth=0):
    global cnt
    if depth==n:
        return

    v+=nums[depth]
    if v==s:cnt+=1

    dfs(v,depth+1) #포함하는경우
    dfs(v-nums[depth],depth+1) #포함안하는경우(다시빼줌)
dfs()
print(cnt)

어렵ㄷ