车票找零

let c = [];

// 乘务员手里5角总价值
let wujiaoRemainNum = 0;

/**
 * @param start 起始递归数字
 * @param wujiaoNum 当前还未上车5角人数
 * @param yiyuanNum 当前还未上车1元人数
 * @param answer_list 存储答案
 */
function dfs(start, wujiaoNum, yiyuanNum, answer_list) {
    if (wujiaoNum == 0 && yiyuanNum == 0) {
        // 一定要保存副本
        answer_list.push(c.slice(0));
        return;
    }

    // 第一个人要么是5角,要么是1元
    for (let i = 0; i <= 1; i++) {
        if (i == 0) {
            if(wujiaoNum >= 1){
                c[start] = 5;
                wujiaoRemainNum += 5;
                dfs(start+1, wujiaoNum-1, yiyuanNum, answer_list);
                wujiaoRemainNum -= 5;
                c[start] = 0;
            }
        }else{
            if(yiyuanNum >= 1 && wujiaoRemainNum >= 5){
                c[start] = 10;
                wujiaoRemainNum -= 5;
                dfs(start+1, wujiaoNum, yiyuanNum-1, answer_list);
                wujiaoRemainNum += 5;
                c[start] = 0;
            }
        }
    }
}


let anster_list = [];
dfs(0, 5, 3, anster_list);
console.log(anster_list);

/**
 [ [ 5, 5, 5, 5, 5, 10, 10, 10 ],
 [ 5, 5, 5, 5, 10, 5, 10, 10 ],
 [ 5, 5, 5, 5, 10, 10, 5, 10 ],
 [ 5, 5, 5, 5, 10, 10, 10, 5 ],
 [ 5, 5, 5, 10, 5, 5, 10, 10 ],
 [ 5, 5, 5, 10, 5, 10, 5, 10 ],
 [ 5, 5, 5, 10, 5, 10, 10, 5 ],
 [ 5, 5, 5, 10, 10, 5, 5, 10 ],
 [ 5, 5, 5, 10, 10, 5, 10, 5 ],
 [ 5, 5, 5, 10, 10, 10, 5, 5 ],
 [ 5, 5, 10, 5, 5, 5, 10, 10 ],
 [ 5, 5, 10, 5, 5, 10, 5, 10 ],
 [ 5, 5, 10, 5, 5, 10, 10, 5 ],
 [ 5, 5, 10, 5, 10, 5, 5, 10 ],
 [ 5, 5, 10, 5, 10, 5, 10, 5 ],
 [ 5, 5, 10, 5, 10, 10, 5, 5 ],
 [ 5, 5, 10, 10, 5, 5, 5, 10 ],
 [ 5, 5, 10, 10, 5, 5, 10, 5 ],
 [ 5, 5, 10, 10, 5, 10, 5, 5 ],
 [ 5, 10, 5, 5, 5, 5, 10, 10 ],
 [ 5, 10, 5, 5, 5, 10, 5, 10 ],
 [ 5, 10, 5, 5, 5, 10, 10, 5 ],
 [ 5, 10, 5, 5, 10, 5, 5, 10 ],
 [ 5, 10, 5, 5, 10, 5, 10, 5 ],
 [ 5, 10, 5, 5, 10, 10, 5, 5 ],
 [ 5, 10, 5, 10, 5, 5, 5, 10 ],
 [ 5, 10, 5, 10, 5, 5, 10, 5 ],
 [ 5, 10, 5, 10, 5, 10, 5, 5 ] ]
 */