[UVa]574:Sum It Up

每個數有 有加或沒有加 兩種狀況，
直接利用遞迴把所有狀況都跑出來看看即可得解。

P.S.
為了避免印出重複的組合，
在你有把某數加進去的情況，
重複再找相同值的數是OK的；
但是若你已經不打算把這個數字加進去的時候，
記得要跳掉所有跟這個數相同值的數。
例.
今天你找到+2，
那麼你可以再繼續遞迴+2沒關係，
這樣不會重複。
除非你是已經打算不再找+2了，
那麼之後都不要讓遞迴再遞到+2。

[C](0.012)

	#include<stdio.h>
	int sum( int t, int now, int nowsum, int suma[], int sump, int x[], int xlimit )
	{
	if( now == xlimit )
	return 0;
	nowsum += x[now];
	int i;
	if( nowsum > t )
	{
	for( i = now+1 ; i < xlimit ; i++ )
	if( x[now] != x[i] )
	break;
	return sum( t, i, nowsum-x[now], suma, sump, x, xlimit );
	}
	else if( nowsum < t )
	{
	if( now == xlimit-1 )
	return 0;
	suma[sump++] = x[now];
	int result = sum( t, now+1, nowsum, suma, sump, x, xlimit );
	for( i = now+1 ; i < xlimit ; i++ )
	if( x[now] != x[i] )
	break;
	result += sum( t, i, nowsum-x[now], suma, sump-1, x, xlimit );
	return result;
	}
	else
	{
	int print = 0;
	for( i = 0 ; i < sump ; i++ )
	{
	if( print )
	printf( "+" );
	printf( "%d", suma[i] );
	print = 1;
	}
	if( print )
	printf( "+" );
	printf( "%d", x[now] );
	printf( "\n" );
	for( i = now+1 ; i < xlimit ; i++ )
	if( x[now] != x[i] )
	break;
	return 1 + sum( t, i, nowsum-x[now], suma, sump, x, xlimit );
	}
	}
	int main()
	{
	int t;
	while( scanf( "%d", &t ) != EOF )
	{
	int n;
	scanf( "%d", &n );
	if( t == 0 && n == 0 )
	break;
	int x[20] = {0};
	int i;
	for( i = 0 ; i < n ; i++ )
	scanf( "%d", &x[i] );
	printf( "Sums of %d:\n", t );
	int suma[20] = {0};
	if( !sum( t, 0, 0, suma, 0, x, n ) )
	printf( "NONE\n" );
	}
	return 0;
	}

view raw UVa574.c hosted with ❤ by GitHub