2817 부분 수열의 합

https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV7IzvG6EksDFAXB#none

재귀로 모든 조합을 만들어 본다. 조합을 만드는 도중 합이 K를 넘어가면 더 이상 만들지 않는다.

#include <cstdio>
 
int t,n,k,a[20],ans;
 
void go(int i,int sum)
{
    if(sum>k || i==n)
    {
        if(sum==k) ans++;
        return;
    }
    go(i+1,sum+a[i]);
    go(i+1,sum);
}
 
int main()
{
    scanf("%d",&t);
    for(int T=1;T<=t;T++)
    {
        scanf("%d %d",&n,&k);
        for(int i=0;i<n;i++)
            scanf("%d",&a[i]);
        go(0,0);
        printf("#%d %d\n",T,ans);
        ans=0;
    }
    return 0;
}