Sticks(3)

ラベリング

前回のような数字のリストを作るために、inputの各値にlabelをつけることにする。たとえば、入力値input配列を

input={ 15, 11, 8, 8, 8, 4, 3, 2, 1 };

とすれば、ラベルは

label={ 0, 0, 0, 0, 0, 0, 0, 0, 0 };

と、最初はゼロにセットしておく。

もし、15-4-1とリストを作れば、15,4,1に対応するラベルを1に書き換える。

input: 15 11  8  8  8  4  3  2  1

label:  1  0  0  0  0  1  0  0  1

このようにして、すべてのlabelを1にすることができれば成功だ。
ラベリングの手順は前回の通り、降順にソートされたinputを、先頭から順に調べる、目標とするstickの長さより短ければラベルリング。stickが完成したらまた先頭に戻り、ラベリングされていない値で同じようにラベリング。すべてのlabelが1になれば終了とすればOK。

ただし、前回書いたように合計が20になるパターンは15-4-1と15-3-2と2種類あるので、15-4-1とラベリングして失敗だと分かった場合、15-3-2へと変更しなければならない。というわけで、ここはスタックを使うか再帰で書くかということになるのだが、配列の値をスタックに積んでいくのは非常にめんどくさい。迷わず再帰！ということになる。