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

문제 링크입니다. https://www.acmicpc.net/problem/1182

1182번: 부분수열의 합

백트리킹을 이용해 푸는 문제입니다.

백트래킹을 통해 모든 경우를 확인해보면 되는 문제입니다.

N개의 정수 중, S값을 만들 수 있는 부분 수열을 구하는 문제입니다.

 

먼저 구할 수 있는 경우는 크게 N가지 입니다.

1. 1개만 사용해 S를 만들 경우

2. 2개만 사용해 S를 만들 경우

.....

N. N개만 사용해 S를 만들 경우

 

즉, 1 ~ N개를 선택하여 만들 수 있는 경우를 전부 구한 뒤, 선택된 수들의 합을 통해 S를 만들 수 있는지를 확인하면 됩니다.

여기서 생각해봐야합니다.

위의 예시를 통해 (-7, -3, -2, 5, 8) 을 생각해보겠습니다.

(-7 , -2 , 8) 과 (8, -2, -7) 은 과연 다른 부분 수열일까? -> 나열된 순서만 다르지 같은 수열입니다.

 

따라서 중복된 경우를 확인할 필요 없이 최소한의 경우만 확인해보면 됨을 알 수 있습니다.

 

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#define INF 987654321

using namespace std;

int N, ans;
long long M;
int map[21];
vector<int> number;
bool check[21];

void back_tracking(int start, int cnt, int select) {
	if (cnt == select) {
		long long sum = 0;
		for (int i = 0; i < number.size(); i++) {
			sum += number[i];
		}
		if (sum == M) ans++;
		return;
	}
	else {
		for (int i = start; i <= N; i++) {
			if (!check[i]) {
				check[i] = true;
				number.push_back(map[i]);
				back_tracking(i, cnt + 1, select);
				number.pop_back();
				check[i] = false;
			}
		}
	}
}

void solve() {
	memset(check, false, sizeof(check));
	for (int i = 1; i <= N; i++) {
		number.push_back(map[i]);
		check[i] = true;
		for (int j = 1; j <= N; j++) {
			back_tracking(i, 1, j);
		}
		check[i] = false;
		number.clear();
	}
	cout << ans;
}

int main()
{
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		cin >> map[i];
	}
	solve();
	return 0;
}

 

 

질문 및 조언 댓글 남겨주세요