排列

描述

示例 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;
};

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

原文地址:https://blog.csdn.net/Tyro_java/article/details/134689827

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任

如若转载,请注明出处:http://www.7code.cn/show_45052.html

如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱suwngjj01@126.com进行投诉反馈,一经查实,立即删除

发表回复

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