백준 부분수열의 합 코드 및 해설 (파이썬)

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

1182번: 부분수열의 합

 

백트래킹으로 풀어보려고 했는데, 일단 내장 combinations 써서 풀었다 .. 

1 ~ N개까지 모든 부분 수열을 구해보고 그 합이 S이면 answer 하나씩 증가해주기 

 

import sys
from itertools import combinations

N,S = map(int, sys.stdin.readline().split())
nums = list(map(int, sys.stdin.readline().split()))

answer = 0
for i in range(1,N+1):
	combs = list(combinations(nums,i))
	for comb in combs:
		if sum(comb) == S:
			answer += 1
print(answer)

 

---

백트래킹 풀이법 추가 

idx를 하나씩 증가시키면서 현재 idx의 숫자를 포함하는 경우와 포함하지 않는 경우 각각을 실행해주면 된다. 

 

import sys

N,S = map(int, sys.stdin.readline().split())
nums = list(map(int, sys.stdin.readline().split()))

count = 0

def backtracking(sum,idx):
	# global keyword allows you to modify the variable outside of the current scope
	global count
	if idx >= N:
		return
	sum += nums[idx]
	if sum == S:
		count += 1 
	# 현재 숫자를 포함하는 경우 
	backtracking(sum, idx+1)
	# 현재 숫자를 포함하지 않는 경우 
	backtracking(sum-nums[idx], idx+1)

backtracking(0,0)
print(count)