https://leetcode-cn.com/problems/permutations-ii/

难度：中等

---

  给定一个可包含重复数字的序列，返回所有不重复的全排列。

示例:

输入: [1,1,2]

输出:

[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

解法1：回溯 + 剪枝

  这题求全排列的步骤与 46.全排列 这题是一样的，区别就是 46. 这题给的数字序列是不含重复的数字，而本题则包含重复数字。

  这样的话，我们只需要在原先的基础上对其进行剪枝即可，将造成重复组合的情况去除。

  考虑一组序列：[2, 2, 1, 1]，标记一下以便区分：[2, 2', 1, 1']，对于这组序列，按照 46. 的思路，会造成重复的情况有在固定索引 0 处的值时，序列中的两个 2 和两个 1 都会造成固定值重复，即 [2, 2', 1, 1'] 、[2', 2, 1, 1']，[1, 2', 2, 1'] 和 [1', 2', 1, 2] ，这样，由于第一个固定的数字就重复，后面的所有组合也都是重复的。

  因此，我们要做的就是让每个索引处固定的值不再重复！

  要做到这样，我们可以借用一个 map，对于每个固定的索引，当一个值是第一次出现时，将其记录在 map 中，而若是遇到了 map 中已经存的值，则说明这个值已经固定过了，跳过它，这样就完成了全排列过程中的去重要求。

  当然，还有一个很耿直的做法就是：还是像 46. 一样计算序列的组合，只在保存每个组合结果时，使用一个 map 记录当前组合是否保存过，若未保存过，则记录到结果数组中。。。

剪枝的 JS 代码：

var permuteUnique = function(nums) {
    let res = [];
    let len = nums.length;

    const swap = (i, j) => {
        let tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    };

    const helper = index => {
        if (index === len) {
            res.push(nums.slice());
            return;
        }

        let map = [];
        for (let i = index; i < len; i++) {
            if (map[nums[i]]) {
                continue;
            }
            map[nums[i]] = 1;
            swap(index, i);
            helper(index+1);
            swap(index, i);
        }
    };

    helper(0);

    return res;
};

牛客网的全排列

题目地址

题目描述

  输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则按字典序打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

**输入描述:**输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。

  相较于 LeetCode 的全排列，这题要求答案需要按照字符序进行排列，因此使用上面的方法并不能满足字符序的要求。

  一个简单的使用回溯输出字符序全排列的方法就是创建一个 visited 数组，每次选取字符时从头到尾遍历一次，跳过已经选取的字符，最后在保存结果时判断一下是否有重复的结果，若无，则保存，有则跳过。

function Permutation(str)
{
    if (str === '') {
        return [];
    }
    let res = [];
    let len = str.length;
    let arr = [];
    let visited = [];

    const dfs = index => {
        if (index === len) {
            let s = arr.join('');
            if (res.indexOf(s) === -1) {
                res.push(s);
            }
            return;
        }
        for (let i = 0; i < len; i++) {
            if (!visited[i]) {
                arr.push(str[i]);
                visited[i] = true;
                dfs(index+1);
                arr.pop();
                visited[i] = false;
            }
        }
    };
    
    dfs(0);
    
    return res;
}