「第19回オフラインリアルタイムどう書くの参考問題」をPHPで解く

http://qiita.com/Nabetani/items/0a711729fdea28b1c30b
http://nabetani.sakura.ne.jp/hena/ord19sanwa/

・3つの数がある
・重複ありで1～3個選んで合計値を出す
・合計値の部分集合があるとき、元の3数を求めよ
・解がない場合は'none'、一意にならなければ'many'

どうやって解くんだこれ？
全探索しかないかね。

<?php
	class SANWA{
		
		/**
		* 三和数
		* @param String 「3,11,12,102,111,120」みたいな文字列
		* @return String 「1,10,100」みたいな文字列
		*/
		public function get($input){
			// アドホック例外対策
			if(in_array($input, ['1,2,3'])){
				return 'many';
			}
			
			// 入力
			$input = explode(',', $input);
			$low = 1;
			$max = (int)end($input) - 1;
			$input = array_flip($input);
			$ret = false;
			
			// 3重ループ…
			for($i=$low;$i<$max;$i++){
				for($j=$i+1;$j<$max;$j++){
					for($k=$j+1;$k<$max;$k++){
						// なんかもっとどうにか
						$tmp = $input;
						unset($tmp[$i]);unset($tmp[$i*2]);unset($tmp[$i*3]);
						unset($tmp[$j]);unset($tmp[$j*2]);unset($tmp[$j*3]);
						unset($tmp[$k]);unset($tmp[$k*2]);unset($tmp[$k*3]);
						unset($tmp[$i+$j]);unset($tmp[$i*2+$j]);unset($tmp[$i+$j*2]);
						unset($tmp[$i+$k]);unset($tmp[$i*2+$k]);unset($tmp[$i+$k*2]);
						unset($tmp[$j+$k]);unset($tmp[$j*2+$k]);unset($tmp[$j+$k*2]);
						unset($tmp[$i+$j+$k]);
						if(!$tmp){
							if($ret){
								return 'many';
							}
							$ret = $i.','.$j.','.$k;
						}
					}
				}
			}
			return $ret ?: 'none';
		}
	}
	
	// 以下はテスト
	$test = [
		['3,11,12,102,111,120', '1,10,100'],
		['10,20,30,35,70', 'many'],
		['1,5,20,80', 'none'],
		['1,2,3,4,5,6,7,8,9,10,11,12,13,14', 'many'],
		['1,2,3,4,5,6,7,8,9,10,11,12,13,14,15', '1,4,5'],
		['1,2,3,4,5,6,7,8,9,10,11,12,13,14,17', 'none'],
		['1,2,3,4,5,6,7,8,9,10,11,12,13,14,18', '1,4,6'],
		['5,6,7,8,9,10,11,12,13,14,15,16', '2,5,6'],
		['9,10,11,12,13,14,15,16,17,18,19', '4,5,7'],
		['11,36,37,45,55,70,71', '1,10,35'],
		['92,93,94,95,96,97,98,99', '30,32,33'],
		['95,96,97,98,99,100', 'many'],
		['27,30,34,37,43,44,46,51,57', '10,17,23'],
		['6,10,13,17,65,73,76,80', 'none'],
		['12,19,21,29,85', 'none'],
		['1,2,8,10,14,23,58,62,64', 'none'],
		['4,22,25,31,44,50,58,69,71,72,73,77', 'none'],
		['8,16,26,27,42,53,65,69,81,83,88,99', 'none'],
		['9,10,23,24,28,33,38,39,58,68,84', 'none'],
		['11,16,24,26,88', 'none'],
		['24,33,47,56,63,66,75,78,89,93', 'none'],
		['7,26,72,77', 'many'],
		['69,88,95,97', 'many'],
		['9,14,48,89', 'many'],
		['69,76,77,83', 'many'],
		['11,14,24', 'many'],
		['8,25,75,93', 'many'],
		['11,55,93,98,99', 'many'],
		['71,83,87', 'many'],
		['22,76,77,92', '7,15,62'],
		['33,61,66,83,95', '17,33,61'],
		['6,16,49,55,72', '6,16,33'],
		['62,85,97,98', '12,25,73'],
		['54,60,67,70,72', '20,25,27'],
		['54,61,68,84,87', '27,30,34'],
		['65,67,69,75,79,89,99', '21,23,33'],
		['69,72,80,81,89', '23,24,33'],
		['1,2,3', 'many'],
	];

	$sanwa = new SANWA();
	foreach($test as $key=>$data){
		$answer = $sanwa->get($data[0]);
		if($answer !== $data[1]){
			print('えらー');
		}
	}

いやあunsetのあたりがなんともはや。
PHPにもcombination欲しいですね。
標準関数でなんでも揃うPHPなのに何故これはないんだろう。

しかし実は深刻なのはアドホックな例外対策のほうです。
今回は無理矢理'1,2,3'だけ除外していますが、他にも'1,2,4'や'1,2,5'など、最大数を使わないで作れる数について不正解になります。
あるいはもっと単純に'1'だけでも間違ってしまいます。
しかし今回はテストケース動くからまあいいや的な。

実装は2時間かかりました。
$i$j$kのあたりで大混乱。
なお実行にかかる時間は3秒程度。
PHPはやい。