Permutations II

    Example

    For numbers the unique permutations are:

    Challenge

    Do it without recursion.

    在上题的基础上进行剪枝，剪枝的过程和 一题极为相似。为了便于分析，我们可以先分析简单的例子，以 [1, 2_1, 2_2] 为例。按照上题 Permutations 的解法，我们可以得到如下全排列。

    1. $$[1, 2_1, 2_2]$$
    2. $$[1, 2_2, 2_1]$$
    3. $$[2_1, 1, 2_2]$$
    4. $$[2_1, 2_2, 1]$$
    5. $$[2_2, 1, 2_1]$$
    6. $$[2_2, 2_1, 1]$$

    首先可以确定 [1, 2_1, 2_2] 是我们要的一个解，此时为 [1, 2_1, 2_2], 经过两次list.pop_back()之后，list为 [1], 如果不进行剪枝，那么接下来要加入list的将为 2_2, 那么我们剪枝要做的就是避免将 2_2 加入到list中，如何才能做到这一点呢？我们仍然从上述例子出发进行分析，在第一次加入 2_2 时，相对应的visited[1]为true(对应 2_1)，而在第二次加入 2_2 时，相对应的为false，因为在list为 [1, 2_1] 时，执行list.pop_back()后即置为false。

    一句话总结即为：在遇到当前元素和前一个元素相等时，如果前一个元素visited[i - 1] == false, 那么我们就跳过当前元素并进入下一次循环，这就是剪枝的关键所在。另一点需要特别注意的是这种剪枝的方法能使用的前提是提供的nums是有序数组，否则无效。

    C++

    Unique Subsets 和 Unique Permutations 的源码模板非常经典！建议仔细研读并体会其中奥义。

    Permutation 的题使用字典序的做法其实更为简单，且为迭代的解法，效率也更高。代码和之前的 Permutations 那道题一模一样。

    Java

    见前一题，略。

    复杂度分析

    略