더하기(DFS)

문제 설명

---

덧셈을 못하는 철수를 공부시키기 위해 자연수들을 주고, 그 중에 몇 개의 수를 골라서 그 합이 K가 될 수 있는지 알아보라고 시켰다. 철수 어머니가 자연수들을 무작위로 선택해서 본인도 가능한지 아닌지 모르고 있다. 어머니가 채점을 할 수 있게 주어진 문제의 답을 찾아주자.

입력 설명

---

첫 번째 줄에 테스트 케이스 개수 T(1≤T≤10)가 주어진다.
두 번째 줄부터 아래 내용이 T개 만큼 주어진다.
첫 줄에 자연수 개수 N(5 <= N <= 20)과 K(1 <= K <= 2,000,000)가 공백으로 구분되어 입력된다.
다음 줄에 N개의 자연수 di(1 <= di <= 100,000)가 공백으로 구분되어 입력된다.

출력 설명

---

T줄에 걸쳐 각 테스트 케이스 별로 주어진 자연수 중 몇 개의 합이 K가 되면 “YES”를 아니면 “NO”를 출력한다.

입력 예시

---

2
5 19
1 2 4 7 10
5 25
1 2 4 7 10

출력 예시

---

YES
NO

#include <stdio.h>
#define MAXN (20)
int N, K;//자연수 개수, 만들값
int A[MAXN + 10];//자연수 값
char *msg[] = {"NO", "YES"};
 
int prefixsum[MAXN + 10];//구간합
 
int DFSmulti(int s, int sum){//시작요소번호, 합
    if (sum > prefixsum[N] - prefixsum[s-1]) return 0;//가지치기, 남은 수를 모두 더해도 sum이 안됨
    if (sum == 0) return 1;//성공
    if (sum < 0) return 0;//실패
 
    for (int i=s; i<=N; i++){
        if (DFSmulti(i+1, sum-A[i])) return 1;//성공
    }
    return 0;//실패
}
 
int DFSbinary(int n, int sum){//요소인덱스, 합
    if (sum > prefixsum[N] - prefixsum[n-1]) return 0;//가지치기, 남은 수를 모두 더해도 sum이 안됨
    if (sum == 0) return 1;//성공
    if (sum < 0) return 0;//실패
    if (n > N) return 0;//범위 벗어남, 실패
 
    if (DFSbinary(n+1, sum-A[n])) return 1;//n번째 요소를 사용하는 경우
    if (DFSbinary(n+1, sum)) return 1;//n번째 요소를 사용하지 않는 경우
    return 0;//실패
}
 
int Solve(){
    //1.구간합 구하기
    for (int i=1; i<=N; i++){
        prefixsum[i] = prefixsum[i-1] + A[i];
    }
    //return DFSmulti(1, K);//시작요소번호, 합
    return DFSbinary(1, K);//요소인덱스, 합
}
 
void InputData(void){
    scanf("%d %d", &N, &K);
    for (int i=1; i<=N; i++){
        scanf("%d", &A[i]);
    }
}
 
int main(void){
    int T, t, ans;
    scanf("%d", &T);
    for (t=1; t<=T; t++){
        InputData();//입력
 
        ans = Solve();//여기서부터 작성
 
        printf("%s\n", msg[ans]);//출력
    }
    return 0;
}