[BOJ알고리즘, C++]#1182_부분 수열의 합, 백트래킹, 조합 백트래킹

 

#1. 문제

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

 

---

 

#2. 풀이

 

1. 백트래킹

[알고리즘]#6_백 트래킹

백트래킹 알고리즘은 문제 해결을 위해 여러 후보를 점진적으로 탐색해 나가는 방법입니다. 백트래킹 알고리즘은 현재 후보 경로가 해결책으로 이어질 수 없다고 판단되면, 이전 레벨로 돌아가 다른 후보 해결책들을 탐색합니다. 백트래킹 알고리즘은 일반적으로 재귀 호출을 활용한 DFS를 통해 구현합니다.

 

2. '조합' 유형의 백트래킹, 다만, '반환'이 없는 백트래킹 설계

1. '조합' 유형의 백트래킹 유형의 문제입니다. 다만, '음수'가 포함되어 있기 때문에, 설령 현재 총합이 5가 되었더라도 현재 경로에 대한 탐색을 계속 진행해야 합니다.
2. 백트래킹에서 '순환 여부' 혹은 '간선의 방향성 유무'에 따라서, 각 정점에 대하여 방문여부를 체크할지 결정합니다. 해당 문제는 부분 수열의 원소들은 중복이 없어야 하기 때문에, '방문 여부'를 체크해 줍니다.

 

---

 

#3. 코드

 

/*
    @문제 : 수열의 부분 수열의 합으로 S값을 만들 수 있는 경우의 수 구하기
    @설명
            1. 백트래킹 - 조합 문제를 생각해보면 된다.
            2. 단, '양수' 뿐만 아니라, '음수'도 존재하기 때문에 현재 총 합이 S와 같을 때 dfs 탐색을 종료하면,
            이후에 또 다른 값들로 다시 S값을 만들 수 있는 경우가 존재할 수 있기 때문에 조심해야한다!

*/

#include <iostream>
#include <vector>
using namespace std;

#define MAX 21

int N, S, ans;
int arr[MAX];
bool visited[MAX];

void dfs(int idx, int sum)
{
    if(sum == S)
    {
        ans++;
        // 여기서 바로 return, 즉 깊이 우선 탐색을 종료하지 않는 것이 포인트다!
    }
    for(int i = idx; i<N; ++i)
    {
        if(!visited[i])
        {
            visited[i] = true;
            dfs(i, sum+arr[i]);
            visited[i] = false;
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> S;

    for(int i=0; i<N; ++i)
    {
        cin >> arr[i];
    }

    dfs(0,0);

    if(S==0) ans--;

    cout << ans;

    return 0;
}

 

---