[백준] 1182 파이썬(python) : 부분수열의 합 - (조합)

1182번: 부분수열의 합

 

 

def dfs(idx, sum):
    global answer
    if(idx >= n): #1
        return
    sum += arr[idx] #2
    if s == sum: #3
        answer += 1
    dfs(idx+1, sum-arr[idx]) #4
    dfs(idx+1, sum) #5

n, s = map(int, input().split())
arr = list(map(int, input().split()))
answer = 0
dfs(0, 0)
print(answer)

 

#1 : 재귀함수 탈출조건(idx가 깊이이고 배열의 idx는 n-1까지 이므로 idx == n이면 탈출)

#2 : 자신의 위치의 값 포함

#3 : 만들 수 있으면 answer +1

#4 : 자신의 위치값을 포함하지 않고 다음 노드로(인덱스로)

#5 : 자신의 위치값 포함하고 다음 노드로

 

 

다른풀이)

 

 

내가 생각해낸 조합을 이용한 풀이인데 설마 이게 되겠어라고 생각했는데 정답이 되었던 풀이법입니다.

 

 

import sys
from itertools import combinations
n, s = map(int, sys.stdin.readline().split())
arr = list(map(int, sys.stdin.readline().split()))
cnt = 0
for i in range(1, n+1): #1
    for j in combinations(arr, i): #2 
        if sum(j) == s: #3
            cnt += 1
print(cnt)

 

 

#1 : 1부터 n까지 반복

#2 : number 리스트에서 i만큼 숫자를 뽑아서 부분수열을 생성

#3 : 부분 수열들의 합이 s와 같으면 cnt +1

그리고 cnt 출력

 

 

n의 범위가 20까지가 최대여서 가능했던것 같습니다.