알고리즘 문제풀이/백준
[백준 1182] 부분수열의 합
m2162003
2020. 11. 5. 21:28
1182번: 부분수열의 합
첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.
www.acmicpc.net
벡터를 사용하지 않고 풀어보기!
s=0일 경우 하나도 안더했을 때도 포함되므로 빼줘야 한다. 왜냐면 부분 수열의 크기가 양수이기 때문이다.
#include <stdio.h>
using namespace std;
int arr[21];
int n, s, answer;
void dfs(int idx, int sum)
{
if (idx > n - 1)
{
if (sum == s)
{
answer++;
}
return;
}
dfs(idx + 1, sum + arr[idx]);
dfs(idx + 1, sum);
}
int main(void)
{
scanf("%d%d", &n, &s);
for (int i = 0; i < n; i++)
{
scanf("%d", &arr[i]);
}
dfs(0, 0);
if (s == 0)
{
answer--;
}
printf("%d\n", answer);
return 0;
}