1182번 부분집합의 합

백트래킹 문제이다.

이 문제에서 기억해야할 것

1. 그 다음 숫자를 더하는 경우, 안 더하는 경우 2가지 모두 생각해야한다.

https://www.acmicpc.net/problem/1182

<정답 코드 첫 번째>

#include <iostream>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
 
using namespace std;
 
int N = 0, S = 0;
 
int num[21] = { 0, };
 
int ans = 0;
 
void DFS(int sum, int pos)
{
    if (pos == N)
    {
        if (sum == S)
        {
            ++ans;
        }
 
        return;
    }
 
    DFS(sum + num[pos], pos + 1); 
    // 바로 그 다음에 있는 숫자를 더하는 경우
 
    DFS(sum, pos + 1);
    // 바로 그 다음에 있는 숫자를 더하지 않는 경우
}
 
int main(void)
{
    scanf("%d %d", &N, &S);
 
    for (int i = 0; i < N; i++)
    {
        scanf("%d", &num[i]);
    }
 
    DFS(0, 0);
 
    if (S == 0) --ans;
 
    // S가 0일 때, 1을 감소해주는 이유는 
    // DFS(0, 1) → DFS(0, 2) → DFS(0, 3) → DFS(0, 4) → DFS(0, 5) 일 경우
    // (= 아예 아무것도 안 더한 경우.왜냐하면 ans가 0부터 시작) 가 있기 때문이다.
 
    printf("%d\n", ans);
 
    return 0;
}

<정답 코드 두 번째>

#include <iostream>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
 
using namespace std;
 
int N = 0, S = 0;
 
int num[21] = { 0, };
 
int ans = 0;
 
void DFS(int sum, int pos)
{
    if (pos >= N) return;
 
    sum += num[pos];
 
    if (sum == S)
    {
        ++ans;
    }
 
    DFS(sum - num[pos], pos + 1);
 
    DFS(sum, pos + 1);
    
}
 
int main(void)
{
    scanf("%d %d", &N, &S);
 
    for (int i = 0; i < N; i++)
    {
        scanf("%d", &num[i]);
    }
 
    DFS(0, 0);
 
    printf("%d\n", ans);
 
    return 0;
}