算法（三）

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int Min = 1e10;
int num;
int sum = 0;
int res;

void dfs(vector<int>& stone, int w, int start, int cnt) {
 if (cnt == num) {
  if (abs(w * 2 - sum) < Min) {
   res = w;
   Min = abs(w * 2 - sum);
  }
 }
 else {
  if (start == stone.size()) return;
  dfs(stone, w, start + 1, cnt);
  dfs(stone, w + stone[start], start + 1, cnt + 1);  
 }
}

int main()
{
 int n;
 cin >> n;
 vector<int> stone(n);
 for (int i = 0; i < n; i++) {
  cin >> stone[i];
  sum += stone[i];
 }
 num = n / 2;
 sort(stone.begin(), stone.end());
 dfs(stone, 0, 0, 0);
 if (res * 2 > sum) cout << sum - res << " " << res << endl;
 else cout << res << " " << sum - res << endl;
    return 0;
}