前两天看到一道小米的面试题

[mskf]

是这样的，如果你玩过 dota2 的话，很简单一句话，n 个球的卡尔有多少个技能

没玩过的话，大概介绍一下，卡尔有三个球，冰球 Q，雷球 W，火球 E，不同的组合对应不同的技能 QQQ （极冷）,QQW （峰哥漫步）,QQE （冰墙）,WWW （磁暴）,WWQ （吹风）,WWE （灵动迅捷）,EEQ （火人）,EEW （陨石）,EEE （天火）,QWE （推波）一共十个技能（不算天赋）

所以说如果卡尔有 4 个球，或者 n 个球，他会有几个技能呢

[jetyang]

说写程序的可以歇歇了，这是笔试里的一道选择题。正解 @chenno9 已经给出来了，当然还有更简洁的通项表达，多看看组合数学和概率论呗

[Ncanback]

排列组合的典型 为什么会想到用回调递归？

[tohert]

我怎么想到的是笛卡尔乘积。。。

[Arxz]

只会用 dp...排列组合想了半天没想出来

[justfan]

```
#include "stdio.h"
void main()
{
char a[3] = {'q', 'w', 'e'};
int i,j,k;
char tmp1, tmp2, tmp3;
for(i=0;i<3;i++)
{
tmp1 = a[i];
for(j=i;j<3;j++)
{
tmp2 = a[j];
for(k=j;k<3;k++)
{
tmp3 = a[k];
printf("%c%c%c\n", tmp1, tmp2, tmp3);
}
}
}
}
```

[mskf]

@justfan 3^3=27>10，所以有重复的，面试题一般不会考这么简单的三重循环

[lxy42]

python 的一个解法：

https://gist.github.com/ausaki/4219b54eb54654216008103c30d93f72

[justfan]

@mskf 不是三重循环 for(j=i;j<3;j++) for(k=j;k<3;k++)

[NBGGA]

你以为他们想考你算法，其实他们只想招个 DotAer🤣

[across]

https://leetcode-cn.com/problems/combinations/

[across]

@across 啊，我忘了，卡尔技能是没有顺序关系的

[isaacpei]

居然没人发 oeis??? 我来补上 http://oeis.org/A001700

[Vitta]

1 技能加攻击，2 技能加速度，3 技能加回血

[VoidChen]

那啥，我没玩过 dota，但是我看你们的描述，你们可能搞错了一点东西，n 个球，有没有限制球能不能重复用，另外就是 n 个球都是什么球，比如 n 个都是冰球，当 n > 2 的时候 1 个技能。我觉得这道题有点问题吧，跟 N 的关系好像就只是是不是＞ 2 了？

[VoidChen]

@VoidChen 或者说 n/3 个技能。。。。。。。。

[VoidChen]

不好意思，，就是排列组合。。我把这道题的意思想成 LOL 的波珠妹了，以为一共就 3 种球。。。。。

[ccpp132]

n 种球每次 m 个就是 C(n + m -1, n)....
高中组合数学知识其实够用了
相当于 x1 + x2 + ... + xn = m 的正整数解的个数，把 m - 1 个隔板和 n 个球放到一起排

[ccpp132]

@mskf @chenno9 帮你们化简了，比较好手算，滑稽

[VagrantSven]

7C3=35，七个球涂黑三个球当分割

[Ginray]

@chenno9 请问 c(n-n,n-1) 这个是代表什么意思，谢谢