一、題目描述

現在有n個物品，每一個物品都有一個價值，現在想將這些物品分給兩個人，要求這兩個人每一個人分到的物品的價值總和相同（個數可以不同，總價值相同即可），剩下的物品就需要扔掉，現在想知道最少需要扔多少價值的物品才能滿足要求分給兩個人。

要求：時間複雜度$O(3^n)$，空間複雜度$O(n)$

輸入描述

第一行輸入一個整數 T，代表有 T 組測試資料。
對於每一組測試資料，一行輸入一個整數 n ，代表物品的個數。

接下來 n 個數，a[i] 代表每一個物品的價值。

1<= T <= 10
1 <= n <= 15
1 <= a[i] <= 100000

輸出描述：

對於每一組測試資料，輸出一個答案代表最少需要扔的價值。

測試用例：

輸入：
1
5
30 60 5 15 30

輸出：20

栗子說明：樣例解釋，扔掉第三個和第四個物品，然後將第一個物品和第五個物品給第一個人，第二個物品給第二個人，每一個人分到的價值為60，扔掉的價值為20。

二、解題思路

dfs遍歷，每個節點的子結點中，有三種情況：給第一個人，給第二個人，丟掉。

幾個變數說明：
n：需要選擇的物品的總共數量。
sum：所有元素的總和。
全域性變數res：找出滿足情況的最值res，min(res, sum - result1 - result2)。

dfs的遞迴邊界是遍歷到最後一個元素，並且結束條件：搜尋到最後一個物品時，判斷res1和res2兩者是否相等，如果相等則記錄並更新res值。

三、C++程式碼

#include <iostream>
#include<vector>
#include<algorithm>
#include<limits.h>
using namespace std;

// 最小扔掉的價值
int res = INT_MAX;
void dfs(vector<int>& nums, int res1, int res2, int sum, int index, int n){
	//一直選到最後一個數位才返回
	if(index == n){
		if(res1 == res2){
			res = min(res, sum - res1 - res2);
			//res = sum - res1 - res2;
		}
		return;
	}
	// 每次的選擇環節都有3種選擇
	dfs(nums, res1 + nums[index], res2, sum, index + 1, n);
	dfs(nums, res1, res2+ nums[index], sum, index + 1, n);
	dfs(nums, res1, res2, sum, index + 1, n);
}

int main (){
	int t;
	cin >> t; // 組數
	while(t--){
		int n;//該組的物品總數
		cin >> n;
		int temp; //當前存入值
		vector<int> nums;
		for(int i =0; i < n ; i++){
			cin >> temp;
			nums.push_back(temp);
		}
		// 計算該組的元素總和
		int sum = 0;
		for(auto i : nums){
			sum += i;
		}
		//vector，res1和res2和index初始都是0，sum需單獨設變數存起來
		dfs(nums, 0, 0, sum, 0, n);
		cout<<res<< endl;
		res = INT_MAX;
	}
	system("pause");
	return 0;
}

Reference

https://www.nowcoder.com/question/next?pid=27972361&qid=1262805&tid=51115874