1182번 - 부분수열의 합 #백트래킹

1182번 부분수열의 합

수열의 부분집합 중 그 합이 주어진 S와 같은 부분집합의 수를 구하는 문제.

• 전체 중 몇개인지 구해야하므로 모든 경우 다 따져야 한다 (완전탐색)
• dfs 나 재귀 이용해 탐색.
• 모든 정점에서 포함 할지 말지 정해야한다.

• 중요한 점은, A 정점의 DFS가 끝날 때마다 A 정점을 방문하기 전 상태로 돌려야 한다 (백트래킹)

#include <iostream>
#include <vector>
using namespace std;
int n, s, val[20];
int cnt = 0, cursum = 0;
void dfs(int cur)
{
    if (cur == n)	//모든 수 봤으면 끝
        return;
    if (cursum + val[cur] == s) // 조건 만족하는 경우
        cnt++;
    dfs(cur + 1); //이번 원소 포함 안하고 실행

    cursum += val[cur];
    dfs(cur + 1);	//포함 하고 실행

    cursum -= val[cur];	//이번 원소 빼서 이전 상태로 되돌린다.
}
int main()
{
    cin >> n >> s;
    for (int i = 0; i < n; i++)
    {
        cin >> val[i];
    }
    dfs(0);
    cout << cnt << '\n';
    return 0;
}