[백준 1182번] 부분수열의 합 C++

www.acmicpc.net/problem/1182

1182번: 부분수열의 합

 

 

프로그래머스에서 DFS관련 문제를 푸는데

뭔가 진행 후 다시 돌아왔을때를 가정해서 카운트를 해야 될 것 같은 문제를 봤었습니다

 

결국 못 풀었고 과연 이러한 문제는 어떻게 풀어야 하나 찾던 중

백트래킹 이라는 알고리즘을 발견했습니다.

 

아직 완벽히 이해가 되진 않았지만 주석에 보이는 그대로 미포함, 포함 상태를 각각 탐색한 후 

포함상태에서 다시 미포함 상태로 바꿔주는게 메인 아이디어인 것 같습니다.

 

조금 더 여러 문제를 풀어봐야겠습니다.

 

 

 

#include <iostream>
#include <vector>
 
using namespace std;
int n, s;
vector<int> v(n);
int sum,cnt;
void dfs(int curr)
{
    if (curr == n) return;
    if (sum + v[curr] == s) cnt++;
    //원소 미포함
    dfs(curr + 1);
 
    //원소 포함
    sum += v[curr];
    dfs(curr + 1);
 
    //되돌리기
    sum -= v[curr];
 
}
int main()
{
    cin >> n >> s;
    for (int i = 0; i < n; i++)
    {
        int a;
        cin >> a;
        v.push_back(a);    
    }
    dfs(0); //인덱스를 기준으로
    cout << cnt;
    return 0;
}