[백트래킹] C11 백준 1182 부분수열의 합 풀이

문제

• 1182

풀이 과정

• 각 원소는 포함되거나 포함되지 않는 경우의 수를 갖고 그 합이 s와 같으면 카운팅
• 크기가 양수인 부분 수열만 계산해야 함
  • 공집합은 제외한다 라는 뜻

#include <stdio.h>

#define MAX 20

int n,s;
int num[MAX];
int result;

void func(int cur, int sum) {
    if (cur == n) {
        if (sum == s) result++;
        return;
    }
    
    func(cur+1, sum);
    func(cur+1, sum+num[cur]);
}

int main() {
    scanf("%d %d", &n, &s);
    for (int i=0; i<n; i++) {
        scanf("%d", &num[i]);
    }
    
    func(0, 0);
    if (s == 0) result--;
    printf("%d", result);
    return 0;
}