排列

描述

示例 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 )回溯1: 基于数组

function permute(nums: number[]): number[][] {
    const res: number[][] = [];
    // 回溯函数
    const backtrack = (path: number[]) => {
        // 满足当前条件
        if(path.length === nums.length) {
            res.push(path);
            return;
        }
        // 遍历
        for(let i = 0; i < nums.length; i++) {
            if(path.includes(nums[i])) continue;
            backtrack(path.concat(nums[i]));
        }
    }
    backtrack([]);
    return res;
}

2 )回溯2: 基于交换

function permute(nums: number[]): number[][] {
    const res: number[][] = [];
    const backtrack = function(start: number) {
        if (start === nums.length - 1) {
            res.push([...nums]);
            return;
        }
        for (let i: number = start; i < nums.length; i++) {
            [nums[i], nums[start]] = [nums[start], nums[i]]; // 交换
            backtrack(start + 1); // 下一个
            [nums[i], nums[start]] = [nums[start], nums[i]]; // 交换撤销
        }
    }
    backtrack(0); // 从 0 开始
    return res;
};

回溯算法递归深度优先遍历之间关系

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注