Combinations

找到 n 中所有 长度为 k 的不重复的组合

 

my solution (60ms, top 99.97%)

通过问题代换, 可以转换成一种很好理解并易于编写的问题

将问题看做 找出范围 n 中所有满足 p(x) 的整数 x

(和 31. Next Permutation 类似, 我是从中得到的启发)

其中 x 一开始为 ∑k << (n - k); [k=1], 即 n = 4, x = 1234

他们都按照一定规律, 满足下一个数比上一个数大

这个规则 p(x) 用语言描述, 就是:

代码描述如下:

combine 和 getNextNums 的逻辑都相当简单, 写起来很容易

 

best solution (56ms)

emmm, 好奇怪啊, 逻辑上来说想的都是一样的, 为什么他少 4ms 呢... ( 或许是因为通过 this 指针获取变量的锅? )

他用递归的形式来实现, 每次递归中会从当前起始索引循环到结束索引

当数组的长度到达 k 的时候, 就返回

值得一提的是, 他用索引的形式避免了那个会被多次修改的 item 以值形式传递

(我放弃使用递归的一部分原因就是因为暂时想不到什么方法避免那个临时的数组, 原来还可以这样...)