AOJ - Problem 1045 : Split Up!

• 問題文

数列(a_1, a_2, ... , a_n)をAとBの2つに分け、Aの総和とBの総和の差が最も少ないときの差を求める問題です。動的計画法を使う問題かと思いきやnが20以下と小さいので深さ優先探索(DFS)で全探索してもAcceptすることができるようです。

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

int n,ans,a[21];
const int INF = 1e+9;

int solve(int i, int A, int B){
	if( i == n ){
		ans = min( ans , abs(A-B) );
	}else{
		solve( i+1 , A+a[i] , B );
		solve( i+1 , A , B+a[i] );
	}
}

int main(){
	while( cin >> n , n ){
		for(int i=0 ; i < n ; i++ ){
			cin >> a[i];
		}
		ans = INF;
		solve( 0 , 0 , 0 );
		cout << ans << endl;
	}
}