Sum It Up

// File Name: /home/bo_jwolf/soj/1030.cpp
// Author: bo_jwolf
// Created Time: 2014年02月03日 星期一 00时31分10秒

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

#define maxn 1005
int num[ maxn ], temp[ maxn ], vis[ maxn ], t, n, flag, ans, sum, cnt;

void Dfs( int ans, int sum ){
	if( sum == t ){
		flag = 0;
		cout << temp[ 0 ];
		for( int i = 1; i < cnt; ++i )
			cout << "+" << temp[ i ];
		cout << endl;
		//return;
	}
	int j;
	for( int i = ans; i < n; ++i ){
		if( !vis[ i ] && sum + num[ i ] <= t ){
			vis[ i ] = 1;
			temp[ cnt++ ] = num[ i ];
			Dfs( i + 1, sum + num[ i ] );
			vis[ i ] = 0;
			cnt--;
			while( i + 1 < n && num[ i ] == num[ i + 1 ] )
				i++;
		}
	}
}	

int main(){
	while( cin >> t >> n ){
		if( !t && !n )
			break;
		for( int i = 0; i < n; ++i )
			cin >> num[ i ];
		flag = 1;
		ans = sum = 0;
		int i;
	//	sort( num, num + n, cmp );
		for( i = 0; i < n; ++i )
			if( num[ i ] <= t )
				break;
		memset( vis, 0, sizeof( vis ) );
		cout << "Sums of " << t << ":" << endl;
		cnt = 0;
		Dfs( i, 0 );
		if( flag )
			puts( "NONE" );
	}
return 0;
}

Sum It Up

原文：http://blog.csdn.net/bo_jwolf/article/details/18905421