Algo Time Complexity Analyze

组合问题的时间复杂度计算：

1-N 中选取 k 个数

选择次数：

$$ C_N^k $$

操作复杂度：(copy k 个数)

$$ k $$

总时间复杂度：

$$ O(kC_N^k) $$

剪枝：

for i := idx; i <= n - (k-len(path));i ++

每进行一次选择，如果当前选择仍有意义，则必须保证剩余选择的数大于仍然需要选择的次数。

$$ N-i+1 >= k - len(path) $$

对于 i 来说，最大能走到的位置就是有效决策的位置。

$$ i <= n-(k-len(path)) + 1 $$ $$ max_i = n-k+1 $$

总时间复杂度：

$$ O(kC_n^k) $$

Note: 剪枝只影响不满足条件的分支，并不能减少组合数。