벡터를 사용하지 않고 풀어보기!
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;
}
'알고리즘 문제풀이 > 백준' 카테고리의 다른 글
[백준 16987] 계란으로 계란치기 (0) | 2020.11.12 |
---|---|
[백준 14891] 톱니바퀴 (0) | 2020.11.07 |
[백준 9663]N-Queen (0) | 2020.11.05 |
[백준 13335] 트럭 (0) | 2020.11.04 |
[백준 13913] 숨바꼭질 4 (0) | 2020.11.01 |
댓글