1846. [算法课回溯] 组合求和

找出所有相加之和为 nk 个数的组合。组合中只允许含有1-9的正整数,并且每种组合中不存在重复的数字。解集不包含重复的组合。

输入

第一行输入一个整数 k \ (2 \leq k \leq 9) 代表组合的数字数目,一个整数 n \ (1 \leq n \leq 50) 代表要求的和。两个整数之间用空格隔开。

保证所有输入都是正整数。

输出

输出所有数字组合。一行代表一个组合,组合内的数字用空格隔开。 当所求和不存在任何组合能相加得到时,输出为0。

如果有多个组合,请按字典序从大到小输出不同的组合。

样例

标准输入 复制文本
3 7
标准输出 复制文本
1 2 4
标准输入 复制文本
3 9
标准输出 复制文本
2 3 4
1 3 5
1 2 6
标准输入 复制文本
3 50
标准输出 复制文本
0
登录以提交代码。
单点时限 1 秒
内存限制 256 MB
提交 889
通过 421