昨天在看王子囤教授写的算法一本书第二章的时候，看到一个地方说Threesum的brutal force解法是N chooses 3(N 是int的个数)，也就是我们平时写的C（N/3）… <—- 土土的写法。
N chooses 3 写开了就是 N(N-1)(N-2)/2*3
突然想到说为什么N chooses 3 的分母是2*3呢？然后就一直想进去了…是笨蛋给自己出的睡前脑筋急转弯><，还特此来写个日记，有够笨诶
所以我的思考过程是这样的：
N chooses 2 打开是N*(N-1)/2， 这个看起来就不那么奇怪了有没有，原因就是第一个选择了N之后第二次只能选择N-1，并且会造成对称的重复（第一次选择A第二次选择B <> 第一次选择B第二次选择A），于是要减少一半。
想通了这个就简单很多呢，那么接下来多选一个会造成怎样的重复呢? 其实超傻的，就是在上面情况里的 AB的前、中、后各多一种重复的可能呀～
嗯更直白一点的说是这样：在已经选择了两个的基础上，多选一个C，那么他可能出现在A前面（CAB），出现在AB中间（ACB），以及B以后（ABC），那么也就是说，需要在N*(N-1)/2的基础上再多增加一项(N-3)/3, N-3便是多增加一个slot所带来的更多组合，而3就是多增加一个slot所带来的重复。
所以推而广之，N chooses 4的话，从3个增加到4个呢，也会增加四种重复的组合呢（DABC，ADBC，ABDC，ABCD）。是不是很直观！
如果需要排列的话，那么所有的可能都不是重复啦！也就什么都不用除，嗯。说完了。
ME-MO 