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

1182 부분수열의 합

문제

---

N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.

입력

---

첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.

출력

---

첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다.

---

풀이)

모든 경우를 다 확인하는 brute force문제이다.

재귀적 방법을 이용하였다. 

예를 들어 5개의 원소가 주어지고 합이 100인 부분수열을 찾는다면

원소	10	20	30	40	50
인덱스	0	1	2	3	4

 

수열 크기 1일때 -> {10},{20},{30},{40},{50} 각자 100과 일치하는 지 확인

수열 크기 2일때 -> {10+20},{10+30},,,,{20+30},{20+40},{20+50},,,,,{40+50} 각자 100과 일치하는 지 확인

.

.

이런 식으로 원소들이 조합될때마다 그 조합의 합들이 찾는 값과 일치하는 지 확인해, 

일치하면 결과값을 1씩 더해주었다.

코드)

#include <stdio.h>
#include <vector>
using namespace std;
 
int n, s;
vector <int> vec;
bool visited[20];
int hop, result;
 
void dfs(int idx) {
    for (int i = idx; i < n; i++) {
        if (visited[i] == true) continue;
        visited[i] = true;
        hop += vec[i]; 
        if (hop == s) {
            result++;
        }
        dfs(i+1);
        hop -= vec[i];
        visited[i] = false;
    }
}
 
int main() {
    scanf("%d %d", &n, &s);
    for (int i = 0; i < n; i++) {
        int temp;
        scanf("%d", &temp);
        vec.push_back(temp);
    }
    dfs(0);
    printf("%d", result);
    return 0;
}

결과)