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]]; // 回溯撤銷
    }
};