입력 | 출력 |
---|---|
5 0 -7 -3 -2 5 8 | 1 |
: combinations 이용
재귀 및 백트래킹으로 풀 수 있다.
어렵다 재귀..
def dfs(idx, sumi):
global cnt
if idx >= n:
return
sumi += nums[idx]
if sumi == s:
cnt += 1
dfs(idx+1, sumi-nums[idx]) # 원소 미포함
dfs(idx+1, sumi) # 원소 포함
n, s = map(int, input().split())
nums = list(map(int, input().split()))
cnt = 0
dfs(0, 0)
print(cnt)
해당 원소를 포함하는 dfs와 포함하지 않는 dfs.