[백준 1182] 부분수열의 합

www.acmicpc.net/problem/1182

1182번: 부분수열의 합

벡터를 사용하지 않고 풀어보기!

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;
}