조합 dfs 형식으로 풀기

#include<iostream>
#include <vector>
#define MAX 17000000
#define CITY 16

using namespace std;

int ans = 0;

//배열, 목표숫자, index, 현재 숫자
void dfs(vector<int> v, int num, int idx, int cur) {

	//나가는 시점: 맞을 때, 초과할 때, 끝에 다다랐을 때
	if (cur == num) {
		ans++;
		return;
	}
	if (cur > num || idx >= v.size()) {
		return;
	}
	
	for (int i = idx + 1; i < v.size(); i++) {
		cur += v[i];
		dfs(v, num, i, cur);
		cur -= v[i];
	}
}

int solve(vector<int> v, int num)
{
	int ret = 0;
	for(int i=0; i<v.size(); i++)
		dfs(v, num, i, v[i]);

	return ret;
}

int main()
{
	vector<int> v = { 1, 2, 4, 5 };
	solve(v, 6);
	cout << ans << "\n";
	ans = 0;

	v = { 1, 3, 4, 7, 8 };
	solve(v, 7);
	cout << ans << "\n";
	ans = 0;

	solve(v, 8);
	cout << ans << "\n";
	ans = 0;
	return 0;
}