求star

全排列(一)#

题目#

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：

输入：nums = [0,1]
输出：[[0,1],[1,0]]

示例 3：

输入：nums = [1]
输出：[[1]]

题解:key:#

回溯:back:#

TIP

​ 将问题看作有 n个空的位置，需要用给定的n个数进行填充，每个数只能用一次。所以可以用穷举法，从左到右每一个位置都尝试填入一个数，看能否填完n个空，如果可以，那么就成为一种符合题意的排列方式

​ 如何确保每个数只使用一次？我们可以很直观的想到维护一个visited标记数组，用来判断某个数字还能否被使用。实际上，我们可以更进一步，去掉标记数组，减少空间开销，将题目给定的nums数组划分成两个部分，左边表示已经填过的数，右边表示待填的数，在回溯的时候动态维护这个数组即可

​ 如果题目要求按照字典序输出结果，那改用标记数组或其他方法即可

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function (nums) {
    const res = []
    const output = JSON.parse(JSON.stringify(nums))
    backTrack(res, nums.length, 0, output)
    return res
};
const swap = (arr, i, j) => {
    [arr[i], arr[j]] = [arr[j], arr[i]]
}
// first表示从左到右填到第first个位置,当前排列为output
const backTrack = (res, n, first, output) => {
    if (first === n) {
        //  注意不要直接把output添加到结果中，否则最后结果中引用的都是同一个数组
        res.push(Array.from(output))
    }
    for (let i = first; i < n; i++) {
        swap(output, i, first)
        backTrack(res, n, first + 1, output)
        swap(output, i, first)
    }
}

全排列(二)#

题目#

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

示例 1：

输入：nums = [1,1,2]
输出：
[[1,1,2],
 [1,2,1],
 [2,1,1]]

示例 2：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

题解:key:#

TIP

​ 此题相对于上一题，只改变了一个条件：给定的序列nums可能包含重复数字。所以解决问题的思路是一致的，只需要进行去重即可

​ 要解决重复问题，我们只要设定一个规则，保证在填第 index个数的时候重复数字只会被填入一次即可。而在本题解中，我们选择对原数组排序，保证相同的数字都相邻，然后每次填入的数一定是这个数所在重复数集合中「从左往右第一个未被填过的数字」

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permuteUnique = function (nums) {
    const res = []
    const n = nums.length
    const visit = new Array(nums.length).fill(false)
    nums.sort((a, b) => a - b)
    const backTrack = (index, output) => {
        if (index === n) {
            res.push(output.slice())
            return
        }
        for (let i = 0; i < n; i++) {
            // 去重
            if (visit[i] || (i > 0 && nums[i] === nums[i - 1] && !visit[i - 1])){
                continue
            }
            output.push(nums[i])
            visit[i] = true
            backTrack(index+1,output)
            visit[i] = false
            output.pop()
        }
    }
    backTrack(0,[])
    return res
};