46、全排列 | 算法（leetcode，附思维导图 + 全部解法）300题

零 标题：算法（leetcode，附思维导图 + 全部解法）300题之（46）全排列

一 题目描述

二 解法总览（思维导图）

三 全部解法

1 方案1

1)代码：

// 方案1 “自己。回溯法（实现：用递归）”。
// 用时：6分钟。

// 思路：
// 1）状态初始化：l = nums.length;
// curList = [], restList = nums, resList = []; 。
// 2）调用回溯函数。
// 3）返回结果 resList 。

// 回溯法框架：
// ```
// result = []
// def backtrack(路径, 选择列表):
//     if 满足结束条件:
//         result.add(路径)
//         return

//     for 选择 in 选择列表:
//         # 做选择
//         路径.add(选择)
//         将该选择从选择列表移除
//         # 核心：递归调用之前【做选择】，调用之后【撤销选择】
//         backtrack(路径, 选择列表) 
//         # 撤销选择
//         路径.remove(选择)
//         将该选择再加入选择列表
// ```
// 参考：
// 1）https://leetcode.cn/problems/permutations/solution/by-huan-huan-20-hblf/
var permute = function(nums) {
    const backtrace = (curList = [], restList = []) => {
        const restListLength = restList.length;
        // 1）递归出口。
        if (restListLength === 0) {
            resList.push(curList.slice());
            return;
        }

        // 2）递归主体。
        for (let i = 0; i < restListLength; i++) {
            const tempVal = restList[i],
                tempRestList = restList.filter((value, index) => index !== i);
            curList.push(tempVal);
            backtrace(curList, tempRestList);
            // 注：清理环境！！
            curList.pop();
        }
    };

    // 1）状态初始化：l = nums.length;
    // curList = [], restList = nums, resList = []; 。
    const l = nums.length;
    let curList = [],
        restList = nums,
        resList = [];

    // 2）调用回溯函数。
    backtrace(curList, restList);

    // 3）返回结果 resList 。
    return resList;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

四 资源分享 & 更多

1 历史文章 - 总览

2 博主简介

码农三少 ，一个致力于编写 极简、但齐全题解（算法） 的博主。
专注于 一题多解、结构化思维 ，欢迎一起刷穿 LeetCode ~