Q48 均等に分配されるカード

JavaScriptのソース

Solve( 3,2);
Solve( 7,2);
Solve(16,4);

function Solve(pM,pN)
{
    //カードの総和の上限
    const SumLimit = pM * (pM + 1) / 2 / pN;

    var Stk = new Array();
    var WillPush = new JyoutaiDef(pM,pN);
    Stk.push(WillPush);

    var Answer = 0;

    while(Stk.length > 0){
        var Poped = Stk.pop();

        //クリア判定
        if(Poped.CurrNum == 0){
            Answer++;
            continue;
        }

        for(var I = 0 ; I <= Poped.CardArr.length - 1 ; I++){
            //配列の総和
            var SumVal = 0;
            for(var J = 0 ; J <= Poped.CardArr[I].length - 1 ; J++){
                SumVal += Poped.CardArr[I][J];
            }

            if(SumVal + Poped.CurrNum > SumLimit) continue;

            WillPush = new JyoutaiDef(pM,pN);
            WillPush.CardArr = GetClone(Poped.CardArr);
            WillPush.CardArr[I] = Poped.CardArr[I].concat(Poped.CurrNum);
            WillPush.CurrNum = Poped.CurrNum - 1;
            Stk.push(WillPush);

            //0件だったらBreak;
            if(Poped.CardArr[I].length == 0) break;
        }
    }
    document.write('M=' , pM ,',N=' , pN , 'だと、' , Answer , '通り<br>');
}

//コンストラクタ
function JyoutaiDef(pM,pN)
{
    this.CardArr = new Array(pN);
    for(var I = 0 ; I <= this.CardArr.length - 1 ; I++){
        this.CardArr[I] = new Array();
    }
    this.CurrNum = pM;
}

//CardArrのクローンを返す
function GetClone(pArr)
{
    var WillReturn = new Array(pArr.length);
    for(var I = 0 ; I <= WillReturn.length - 1 ; I++){
        WillReturn[I] = pArr[I].concat();
    }
    return WillReturn;
}

実行結果

M=3,N=2だと、1通り
M=7,N=2だと、4通り
M=16,N=4だと、2650通り

解説

深さ優先探索で解いてます。