dfs

 avatar
user_8384735
c_cpp
2 years ago
1.2 kB
7
Indexable
Never
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 70;
int t[N], vis[N];
int n, sum, target, patt, ans;
bool cmp(int x, int y){
	return x > y;
}
bool dfs(int res, int x, int index){
	if (x == target)
	{
		if (patt == ++res){
			ans = target;
			return 1;
		}
		for (index = 0; vis[index]; index++);
		vis[index] = 1;
		return vis[index] = dfs(res, t[index], index + 1);

	}
	for (int i = index; i < n; i++){
		if (vis[i] || x + t[i] > target) continue;
		if (i ^ index && t[i] == t[i - 1] && !vis[i - 1]) continue;
		vis[i] = 1;
		if (dfs(res, x + t[i], i + 1))
			return 1;
		vis[i] = 0;
		if (x + t[i] == target) return 0;
	}
	return 0;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
	while (cin >> n, n){
		sum = 0;
		for (int i = 0; i < n; i++)
			cin >> t[i] , sum += t[i];
		sort(t, t + n, cmp);
		//reverse(t, t + n);
		ans = sum;
		for (int i = t[0]; i <= sum / 2; i++){
			if (sum % i)continue;
			target = i;
			memset(vis, 0, sizeof(vis));
			vis[0] = 1, patt = sum / i;
			if (dfs(0,t[0], 1))
				break;
		}
		cout << ans << endl;
	}
}