0043 - Puzzle

#include <iostream>
#include <string>
using namespace std;

int Check(int number[])	{
	int sum=0;

	for (int i=1; i<10; ++i)
		sum+=number[i];
	return sum;
}

void dfs(int number[], bool answer_flg[], int i)	{
	if ( !Check(number) )	answer_flg[i]=true;
	else	{
		for (int j=1; j<10; ++j)
			if (number[j] >= 3)	{
				number[j]-=3;
				dfs(number,answer_flg,i);
				number[j]+=3;
			}
		for (int j=3; j<10; ++j)
			if (number[j-2]>=1 && number[j-1]>=1 && number[j]>=1)	{
				--number[j-2]; --number[j-1]; --number[j];
				dfs(number,answer_flg,i);
				++number[j-2]; ++number[j-1]; ++number[j];
			}
	}
}

void Slove(string hand)	{
	int number[10]={0};
	bool answer_flg[10]={false}, kong_flg=false, flg=false;

	for (int i=0; i<hand.size(); ++i)
		++number[hand[i]-'0'];
	for (int i=1; i<10; ++i)	{
		if (number[i] == 4)	kong_flg=true;
		else
			for (int j=1; j<10; ++j)	{
				++number[i];
				if (number[j] >= 2)	{
					number[j]-=2;
					dfs(number,answer_flg,i);
					number[j]+=2;
				}
				--number[i];
			}
	}
	for (int i=1; i<10; ++i)
		if ( answer_flg[i] )	{
			if (!flg)	{
				cout << i;
				flg=true;
			}
			else	cout << " " << i;
		}
	if (!flg)	cout << "0";
	cout << endl;
}

int main(void)	{
	string hand;

	while (cin >> hand)
		Slove(hand);
	return 0;
}

再帰で全探索。