题解思路

问题描述

圣诞节，圣诞老人有 n 件礼物要分给 k 个小朋友。我们需要计算出所有可能的分配方式，输出分配的总数，并且列出每一种分法。

每个小朋友可以获得任意数量的礼物（包括0件），并且所有的礼物是无差别的。

解题思路

1. 递归与回溯
   使用递归生成所有可能的分法。每个递归的步骤是尝试给某个小朋友分配一定数量的礼物，剩下的礼物继续递归分配给其余的小朋友。每次递归时，剩余的礼物数 n 会逐渐减少。

题目内容

圣诞节到了，城堡里有 $k$ 个小朋友，圣诞老人魔法口袋里带了 $n$ 件无差别的小礼物。请帮圣诞老人处理：将 $n$ 个无差别的礼物分给 $k$ 个小朋友的分法问题。

给定 $n$ 和 $k$ ，输出分法总数，并枚举出所有的分法。

输入描述

仅一行，包含 $2$ 个整数 $n(0<=n<=10)$ 和 $k(1<=k<=10)$ ，$n$ 表示礼物的数量，$k$ 表示小朋友的数量。

输出描述

第一行输出分法总数 $t$

后须 $t$ 行依次列出每种分法：每件礼物用字符 $'*'$ ($ascii$ 码为 $42$ )表示，用字符 $'|'$ ($ascii$ 码为 $124$ )分隔小朋友。具体输出和顺序请参考样例

样例1

输入

3 2

输出

4
***|
**|*
*|**
|***

说明

第一行表示 $3$ 件礼物分给 $2$ 个小朋友的分法一共有 $4$ 种

第二行表示第一个小朋友分有 $3$ 件礼物，第二个小朋友无礼物，以 $'|'$ 分隔

第三行表示第一个小朋友分有 $2$ 件礼物，第二小朋友分有 $1$ 件礼物， 以$'|'$ 分隔

第四行表示第一个小朋友分有 $1$ 件礼物，第三小朋友分有 $2$ 件礼物，以 $'|'$ 分隔

第五行表示第一个小朋友无礼物，第二小朋友分有 $3$ 件礼物， 以$'|'$ 分隔