46.全排列

LeetCode LeetCode 深度优先搜索 热题100 回溯 排列
发布时间 :
字数:1.6k 阅读 : 评论:
  1. 46.全排列
    1. 46.1 题目
    2. 46.2 题解
      1. 方法一：回溯法（深度优先搜索 DFS）
        1. 思路
        2. 复杂度分析
        3. 代码
    3. 46.3 代码
    4. 46.4 运行结果

46.全排列

46.1 题目

给定一个不含重复数字的数组 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 中的所有整数互不相同

46.2 题解

方法一：回溯法（深度优先搜索 DFS）

思路

全排列就是尝试每个位置放不同的数字。回溯法的核心：「选择 → 递归 → 撤销选择」

用 path 记录当前排列，used 数组标记哪些数字已经用过。

当 path 长度等于数组长度时，说明凑出了一个完整排列。

举个例子：nums = [1,2,3]

开始：path=[], used=[F,F,F]
选择1：path=[1], used=[T,F,F]
  选择2：path=[1,2], used=[T,T,F]
    选择3：path=[1,2,3] ✓ 加入结果
  撤销2，选择3：path=[1,3], used=[T,F,T]
    选择2：path=[1,3,2] ✓ 加入结果
撤销1，选择2：path=[2], used=[F,T,F]
  ...继续类似过程

复杂度分析

  • 时间复杂度：O(n × n!)
  • 空间复杂度：O(n)

代码

// 方法：回溯法（深度优先搜索 DFS）
// 核心思想：通过「尝试-回溯」的方式，逐个位置填充数字，直到所有位置填满得到一个排列
// 1. 使用 path 记录当前正在构建的排列
// 2. 使用 used 数组标记数字是否已被使用（避免重复使用）
// 3. 当 path 长度等于 nums 长度时，说明得到一个完整排列，加入结果集
static IList<IList<int>> Permute(int[] nums)
{
    IList<IList<int>> result = new List<IList<int>>();
    if (nums == null || nums.Length == 0) return result;

    int len = nums.Length;
    bool[] used = new bool[len]; // 标记数字是否已被使用
    List<int> path = new List<int>(); // 记录当前正在构建的排列

    // 启动回溯
    Backtrack(nums, len, path, used, result);
    return result;
}

// 回溯辅助函数
// nums：原始数组
// len：数组长度（避免重复计算）
// path：当前正在构建的排列
// used：数字使用标记
// result：结果集
static void Backtrack(int[] nums, int len, List<int> path, bool[] used, IList<IList<int>> result)
{
    // 终止条件：当前排列长度等于数组长度，说明得到一个完整排列
    if (path.Count == len)
    {
        result.Add(new List<int>(path)); // 注意：要 new 一个新列表加入结果，避免后续修改影响
        return;
    }

    // 遍历所有数字，尝试将未使用的数字加入当前排列
    for (int i = 0; i < len; i++)
    {
        // 如果当前数字已被使用，跳过
        if (used[i]) continue;

        // 1. 选择：将当前数字加入排列，并标记为已使用
        path.Add(nums[i]);
        used[i] = true;

        // 2. 递归：继续构建下一个位置的数字
        Backtrack(nums, len, path, used, result);

        // 3. 回溯：撤销选择，将当前数字从排列中移除，并标记为未使用
        path.RemoveAt(path.Count - 1);
        used[i] = false;
    }
}

46.3 代码

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        #region 题目

        // 给定一个不含重复数字的数组 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 中的所有整数互不相同

        #endregion

        #region 测试

        // 示例 1
        int[] nums1 = { 1, 2, 3 };
        IList<IList<int>> result1 = Permute(nums1);
        Console.WriteLine($"示例1 回溯 方法 输出：{FormatList(result1)}");

        // 示例 2
        int[] nums2 = { 0, 1 };
        IList<IList<int>> result2 = Permute(nums2);
        Console.WriteLine($"示例2 回溯 方法 输出：{FormatList(result2)}");

        // 示例 3
        int[] nums3 = { 1 };
        IList<IList<int>> result3 = Permute(nums3);
        Console.WriteLine($"示例3 回溯 方法 输出：{FormatList(result3)}");

        #endregion
    }

    #region 辅助方法

    // 辅助方法：格式化排列结果为字符串，方便输出
    static string FormatList(IList<IList<int>> list)
    {
        if (list == null || list.Count == 0) return "[]";
        List<string> permutationStrings = new List<string>();
        foreach (var perm in list)
        {
            permutationStrings.Add($"[{string.Join(",", perm)}]");
        }

        return $"[{string.Join(",", permutationStrings)}]";
    }

    #endregion

    #region 答案

    // 方法：回溯法（深度优先搜索 DFS）
    // 核心思想：通过「尝试-回溯」的方式，逐个位置填充数字，直到所有位置填满得到一个排列
    // 1. 使用 path 记录当前正在构建的排列
    // 2. 使用 used 数组标记数字是否已被使用（避免重复使用）
    // 3. 当 path 长度等于 nums 长度时，说明得到一个完整排列，加入结果集
    static IList<IList<int>> Permute(int[] nums)
    {
        IList<IList<int>> result = new List<IList<int>>();
        if (nums == null || nums.Length == 0) return result;

        int len = nums.Length;
        bool[] used = new bool[len]; // 标记数字是否已被使用
        List<int> path = new List<int>(); // 记录当前正在构建的排列

        // 启动回溯
        Backtrack(nums, len, path, used, result);
        return result;
    }

    // 回溯辅助函数
    // nums：原始数组
    // len：数组长度（避免重复计算）
    // path：当前正在构建的排列
    // used：数字使用标记
    // result：结果集
    static void Backtrack(int[] nums, int len, List<int> path, bool[] used, IList<IList<int>> result)
    {
        // 终止条件：当前排列长度等于数组长度，说明得到一个完整排列
        if (path.Count == len)
        {
            result.Add(new List<int>(path)); // 注意：要 new 一个新列表加入结果，避免后续修改影响
            return;
        }

        // 遍历所有数字，尝试将未使用的数字加入当前排列
        for (int i = 0; i < len; i++)
        {
            // 如果当前数字已被使用，跳过
            if (used[i]) continue;

            // 1. 选择：将当前数字加入排列，并标记为已使用
            path.Add(nums[i]);
            used[i] = true;

            // 2. 递归：继续构建下一个位置的数字
            Backtrack(nums, len, path, used, result);

            // 3. 回溯：撤销选择，将当前数字从排列中移除，并标记为未使用
            path.RemoveAt(path.Count - 1);
            used[i] = false;
        }
    }

    #endregion
}

46.4 运行结果

示例1 回溯 方法 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,2,1],[3,1,2]]
示例2 回溯 方法 输出：[[0,1],[1,0]]
示例3 回溯 方法 输出：[[1]]
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com

赏

©2016-2026 Tao

Built with Hexo and 3-hexo theme

×

喜欢就点赞,疼爱就打赏