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

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

1182번: 부분수열의 합

🔔 문제 : 

N ( 1<= N <=20), |S| <= 1,000,000, |X| <= 100,000 범위의 조건에서

 

정수 X가 N개 만큼 제공 됩니다. 이때.  이 순열의 부분집합을 뽑아서 합이 S가 되는 개수를 출력하면 되는 문제입니다.

 

예를 들어 입력이 N = 5,  S = 0 , X = {-7, -3, -2, 5, 8} 인경우

5 0
-7 -3 -2 5 8

 

출력은 -3 -2 5 로 한개가 됩니다.

---

🔔 Kick Point :

숫자를 뽑는 것이기 때문에 1부터 N개 만큼 DFS(백트래킹)을 돌려서 개수를 찾으면 됩니다.

 

조합(combination)을 DFS(깊이우선탐색) 백트래킹을 사용하는 법을 더 자세히 알고싶다면, 이 포스팅을 참고해주세요

2022.03.03 - [백준] - [C++][백준] - N과 M (2) (15650번)

[C++][백준] - N과 M (2) (15650번)

 

---

🔔 Code :

#include <iostream>
using namespace std;

int G_N;
int G_S;
int G_sequence[21];
int G_Result = 0;

bool visited[21] = {false, };

void DFS(int dest, int cnt = 0, int n = 1){

	if (cnt == dest) {
		int tmp = 0;
		
		for (int i = 1; i <= G_N; i++) {
			if (visited[i]) tmp += G_sequence[i];
		}
		
		if (tmp == G_S) ++G_Result;
		return;
	}

	for (int i = n; i <= G_N; i++) {

		if (!visited[i]) {
			visited[i] = true;
			DFS(dest, cnt + 1, i + 1);
			visited[i] = false;
		}
	}
}

void Sol() {

	for (int i = 1; i <= G_N; i++) {
		DFS(i);
	}
}

int main() {
	cin >> G_N >> G_S;
	for (int i = 1; i <= G_N; i++) {
		cin >> G_sequence[i];
	}

	Sol();

	cout << G_Result;

}

 

---