문제
접근
각 원소를 더하거나 더하지 않는 모든 경우의 수를 탐색하는 방법으로 해결할 수 있다.
원소에 음수도 포함되어 있기 때문에 마지막까지 탐색해봐야 결과를 알 수 있음
마지막에 s가 0인 경우는 아무거도 더하지 않은 경우에도 성립되므로, 결과에서 1을 빼줌
코드
- C++ 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<iostream>
using namespace std;
int func(int nowIdx, int sum);
int arr[30];
int n, s;
int main() {
cin >> n >> s;
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
int result = func(0, 0);
if (s == 0)
result--;
cout << result;
return 0;
}
int func(int nowIdx, int sum) {
if (n == nowIdx) {
if (sum == s) return 1;
else return 0;
}
return func(nowIdx + 1, sum) + func(nowIdx + 1, sum + arr[nowIdx]);
}
- 파이썬 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import sys
def func(idx, nowSum):
if n == idx:
if s == nowSum:
return 1
else:
return 0
return func(idx+1, nowSum) + func(idx+1,nowSum+arr[idx])
n, s = map(int, input().split())
arr = list(map(int, input().split()))
result = func(0,0)
if s == 0:
result-=1
print(result)