LeetCode46 全排列

LeetCode 全排列

• 题目
• 解题
• • 解题一：从第 n-1 个字符的排列组合开始构造
  • 解题二：从 n-1 个字符的所有子序列的排列组合开始构建
  • 解题三：回溯写法

题目

解题

解题一和二的解法思路可以参考：LeetCode《程序员面试金典》面试题 08.07. 无重复字符串的排列组合

解题一：从第 n-1 个字符的排列组合开始构造

// javascript
var permute = function(nums) {
    let perms = [];
    if (nums.length === 0) {
        perms.push([]);
        return perms;
    }
    let first = nums[0], remainder = nums.slice(1);
    let arrs = permute(remainder);
    for (let arr of arrs) {
        for (let i = 0; i <= arr.length; i++) {
            let newArr = insertNumAt(arr, first, i);
            perms.push(newArr);
        }
    }
    return perms;
};

var insertNumAt = function(arr, num, index) {
    let before = arr.slice(0, index);
    let after = arr.slice(index);
    return before.concat(num, after);
}
           

解题二：从 n-1 个字符的所有子序列的排列组合开始构建

// javascript
var permute = function(nums) {
    let perms = [];
    if (nums.length === 0) {
        perms.push([]);
        return perms;
    }
    for (let i = 0; i < nums.length; i++) {
        let num = nums[i];
        let before = nums.slice(0, i);
        let after = nums.slice(i + 1);
        let arrs = permute(before.concat(after));
        for (let arr of arrs) {
            perms.push([num].concat(arr)); // 要将 num 构造成数组才能用 concat
        }
    }
    return perms;
};
           

调用栈来传递 path：

// javascript
var permute = function(nums) {
    let perms = new Array();
    getPerms([], nums, perms);
    return perms;
};

var getPerms = function(path, nums, perms) {
    if (nums.length === 0) perms.push(path);
    for (let i = 0; i < nums.length; i++) {
        let before = nums.slice(0, i);
        let after = nums.slice(i + 1);
        let num = nums[i];
        getPerms(path.push(num), before.concat(after), perms);
    }
};
           

解题三：回溯写法

详细分析见：全排列。构造的方法同解法二，只是这一次没有在递归调用时传入新构造的 nums（里面全是还没有被使用过的数字），而是改用 used 来进行记录（视频解法）：

// javascript
var permute = function(nums) {
    let perms = new Array(), path = new Array();
    let used = new Array(nums.length).fill(false);
    dfs(nums, 0, used, path, perms);
    return perms;
};

var dfs = function(nums, depth, used, path, perms) {
    if (depth === nums.length) {
        perms.push(path.slice());
        return;
    }
    for (let i = 0; i < nums.length; i++) {
        if (used[i] === true) continue;
        path.push(nums[i]);
        used[i] = true;
        dfs(nums, depth + 1, used, path, perms);
        // 回溯撤销
        path.pop();
        used[i] = false;
    }
};
           

文字解法没有使用额外的 used 和 path，而是用 nums 的左侧存储 已经确立过的 path，右侧的则是尚未使用过的数字：

// javascript
var permute = function(nums) {
    let perms = new Array();;
    dfs(nums, 0, perms);
    return perms;
};

var dfs = function(nums, depth, perms) {
    if (depth === nums.length) {
        perms.push(nums.slice());
        return;
    }
    for (let i = depth; i < nums.length; i++) {
        [nums[depth], nums[i]] = [nums[i], nums[depth]];
        dfs(nums, depth + 1, perms);
        [nums[i], nums[depth]] = [nums[depth], nums[i]]; // 回溯撤销
    }
};