Algo Time Complexity Analyze

回溯

1-N 中选取 k 个数

选择次数：$C_N^k$

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

总时间复杂度：$O(kC_N^k)$

剪枝：

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

每进行一次选择，如果当前选择仍有意义，则必须保证剩余选择的数大于仍然需要选择的次数。对于 i 来说，最大能走到的位置就是有效决策的位置。

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

总时间复杂度：$O(kC_n^k)$

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

Case A:
[1,2,3] -> [1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,2,1],[3,1,2]
Case B:
[1,1,2] -> [1,1,2],[1,2,1],[2,1,1]

注意 Case B：

全排列问题的起始索引位都为$0$, 通过 used 位数组判断某个元素是否被取过，对于 [1,1,2] 来说，我们只需要关注第二个1一定在第一个1后面即可，也就是说：如果1a被取过，我们就取1b，使得一定不会先取1b，即可满足不重复。

if used[i] || i > 0 && nums[i] == nums[i - 1] && !used[i-1] {
    continue //不取
}