当前位置：首页 > article >正文

【数据结构与算法】力扣 46. 全排列

article 2024/10/25 15:10:37

回溯算法

一般回溯的逻辑放在递归函数的下面。这是一种效率低纯暴力的解法，且没有其它的更好的解法。

其核心思想是尝试构建一个解的过程，逐步推进，并在发现当前部分解无法生成一个完整解时，进行回溯，即撤销最近的选择，然后尝试其他可能的选择。

常见场景：

排列问题（有序）
组合问题（无序）
切割问题（比如切割字符串）
子集问题
棋盘问题（N皇后、解数独）

模板伪代码：

function backtrack(解的当前状态):
    if 当前状态是一个解:
        保存解
        return
    
    for 所有可能的选择 in 当前状态的选项集合:
        做选择
        backtrack(更新后的状态)
        撤销选择

题目描述

给定一个不含重复数字的数组 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]]

提示：

1 <= nums.length <= 6
-10 <= nums[i] <= 10
nums 中的所有整数 互不相同

分析解答

很明显这是一道排列问题，遇到排列问题，最先想到的应该就是回溯算法。

参数说明：

path：每次遍历的一个结果集
used：对元素做标记，避免重复使用

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function(nums) {
    const results = []; // 存储最终的全排列结果

    function backtrack(path, used) {
        // 如果当前路径长度等于输入数组长度，说明已经形成了一个完整的排列
        if (path.length === nums.length) {
            results.push([...path]); // 将当前排列添加到结果中
            return;
        }

        // 遍历每个数字 排列和顺序有关 所以总是从 0 开始
        for (let i = 0; i < nums.length; i++) {
            // 如果当前数字已经被使用过，则跳过
            if (used[i]) continue;

            // 选择当前数字
            path.push(nums[i]);
            used[i] = true;

            // 递归调用，继续选择下一个数字
            backtrack(path, used);

            // 撤销选择（回溯），准备尝试下一个可能的数字
            path.pop();
            used[i] = false;
        }
    }

    // 初始化递归调用
    backtrack([], Array(nums.length).fill(false));
    return results;
};