内卷之源：
暫無
題目描述：
* 聖誕節到了，城堡裡有k個小朋友，聖誕老人魔法口袋裡帶了n件無差别的小禮物。
* 請幫聖誕老人處理：将n個無差别的禮物分給k個小朋友的分法問題。
*
* 輸入描述：
* 僅一行，包含2個整數 n(0<=n<=10) 和 k(1<=k<=10)，n表示禮物的數量，k表示小朋友的數量
* 輸出描述：
* 第一行輸出分法總數t
* 後續t行依次列出每種分法：每件禮物用字元‘*’(ascii碼為42)表示，用字元‘|’(ascii碼為124)分隔小朋友。具體輸出和順序請參考示例。
測試用例：
* 示例一：
* 輸入 3 2
* 輸出 4
* ***| //給第一個小朋友分3件，給第二個小朋友分0件
* **|* //給第一個小朋友分2件，給第二個小朋友分1件
* *|** //給第一個小朋友分1件，給第二個小朋友分2件
* |*** //給第一個小朋友分0件，給第二個小朋友分3件
* 示例二：
* 輸入 4 3
* 輸出 15
* ****|| //給第一個小朋友分4件，給第二個小朋友分0件，給第三個小朋友分0件
* ***|*| //給第一個小朋友分3件，給第二個小朋友分1件，給第三個小朋友分0件
* ***||* //給第一個小朋友分3件，給第二個小朋友分0件，給第三個小朋友分1件
* **|**| //給第一個小朋友分2件，給第二個小朋友分2件，給第三個小朋友分0件
* **|*|* //給第一個小朋友分2件，給第二個小朋友分1件，給第三個小朋友分1件
* **||** //給第一個小朋友分2件，給第二個小朋友分0件，給第三個小朋友分2件
* *|***| //給第一個小朋友分1件，給第二個小朋友分3件，給第三個小朋友分0件
* *|**|* //給第一個小朋友分1件，給第二個小朋友分2件，給第三個小朋友分1件
* *|*|** //給第一個小朋友分1件，給第二個小朋友分1件，給第三個小朋友分2件
* *||*** //給第一個小朋友分1件，給第二個小朋友分0件，給第三個小朋友分3件
* |****| //給第一個小朋友分0件，給第二個小朋友分4件，給第三個小朋友分0件
* |***|* //給第一個小朋友分0件，給第二個小朋友分3件，給第三個小朋友分1件
* |**|** //給第一個小朋友分0件，給第二個小朋友分2件，給第三個小朋友分2件
* |*|*** //給第一個小朋友分0件，給第二個小朋友分1件，給第三個小朋友分3件
* ||**** //給第一個小朋友分0件，給第二個小朋友分0件，給第三個小朋友分4件
思路分析：
* 根據輸出格式可知，第一個小朋友的禮物數量按總數遞減。第(k-1)個小朋友的禮物數量每次是基于分給第(k-2)個小朋友剩餘的數量遞減（顯然需使用dfs）。前面所有小朋友分完後剩餘的全分給最後一個小朋友。
* 另可以歸納出的是：
(1)以字元串輸出具體分法，字元串長度固定是(n+k-1)，其中字元‘*’的個數為(n)，字元‘|’的個數為(k-1)。
(2)輸入的n可為0，k可為1，此時分法均隻有一種。（該情形一般dfs應該涵蓋進去）
程式設計實作(C++)：
/*
************************************************************
* @author SLF
* @version V1.0.0
* @date xx-xx-2020
************************************************************
*/
#include <iostream>
#include <string>
#include <vector>
using namespace::std;
void dfs(vector<string> &out, string method, const int &LEN, const int &n, const int &k, const int &index);
int main(void)
{
int n, k;
cin >> n >> k;
// if (0 == n)
// {//禮物數量為0
// cout << 1 << endl;
// for (int i = k-1; 0 < i; ++i)
// {//當k=1時是否該輸出字元'|' ？
// cout << '|';
// }
// cout << endl;
// return 0;
// }
// if (1 == k)
// {//人數為1
// cout << 1 << endl;
// for (; 0 < n; --n)
// {
// cout << '*';
// }
// cout << endl;
// return 0;
// }
const int LEN = n + k -1;
vector<string> out;
dfs(out, "", LEN, n, k-1, 0);
cout << out.size() << endl;
for (const auto &str : out)
{
cout << str << endl;
}
return 0;
}
//第二個形參不能使用引用
void dfs(vector<string> &out, string method, const int &LEN, const int &n, const int &k, const int &index)
{
if (LEN == index)
{
out.push_back(method);
return;
}
if (0 < n)
{
dfs(out, method + '*', LEN, n -1, k, index +1); // method + '*' 并不會改變本層的method字元串，隻會改變下一層
}
if (0 < k)
{
dfs(out, method + '|', LEN, n, k -1, index +1); // method + '|' 并不會改變本層的method字元串，隻會改變下一層
}
}
鄭重提示：①解題思路非最優，覆寫條件可能不全，僅供練習參考。
②若有更佳思路或疑問，可在評論區留言互相讨論，不亦樂乎。
③本文不允許轉載，若認可本文，可點贊收藏關注。