[백준/Python] 1182번(브루트포스, 백트래킹)_부분수열의 합

📌문제 유형

브루트포스 알고리즘, 백트래킹 (실버2)

 

📌문제

1182번: 부분수열의 합

 

📌나의 문제풀이

from itertools import combinations

n, s = map(int,input().split())
num_list = list(map(int,input().split()))
ans = 0

for i in range(1, n+1):
    li = list(combinations(num_list, i))
    for j in range(len(li)):
        if sum(li[j]) == s:
            ans += 1

print(ans)

 

📌 다른사람의 문제풀이

[백준] 1182번 부분수열의 합 - 파이썬(Python)

import sys
input = sys.stdin.readline
n, s = map(int, input().split())
arr = list(map(int, input().split()))
cnt = 0

def subset_sum(idx, sub_sum):
    global cnt

    if idx >= n:
        return

    sub_sum += arr[idx]

    if sub_sum == s:
        cnt += 1
    
    # 현재 arr[idx]를 선택한 경우의 가지
    subset_sum(idx+1, sub_sum)

    # 현재 arr[idx]를 선택하지 않은 경우의 가지
    subset_sum(idx+1, sub_sum - arr[idx])

subset_sum(0, 0)
print(cnt)

 

📌 리뷰 

- N이 20개로 작은 편이어서 combination 이용 가능, 숫자가 크면 이용 못하므로 DFS로 완탐하는 방법도 생각하기