Medium

题目描述

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

解题思路

全排列问题是经典的回溯算法应用场景。主要有两种常见解法：

解法一：回溯 + 标记数组 使用一个布尔数组标记已使用的元素，每次递归选择未使用的元素加入当前排列。当排列长度等于原数组长度时，说明找到一个完整排列。

解法二：回溯 + 交换（推荐） 通过交换元素位置来生成排列，不需要额外的标记空间。将当前位置与后续所有位置（包括自己）交换，递归处理下一位置，回溯时再交换回来。这种方法空间复杂度更优。

核心思想是：对于每个位置，尝试放入所有可能的元素，递归处理剩余位置，完成后回溯到上一状态。

以下代码采用解法二，通过原地交换实现，既简洁又高效。

代码实现

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> result;
        backtrack(nums, 0, result);
        return result;
    }
    
private:
    void backtrack(vector<int>& nums, int start, vector<vector<int>>& result) {
        if (start == nums.size()) {
            result.push_back(nums);
            return;
        }
        
        for (int i = start; i < nums.size(); i++) {
            swap(nums[start], nums[i]);
            backtrack(nums, start + 1, result);
            swap(nums[start], nums[i]);
        }
    }
};

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        def backtrack(start):
            if start == len(nums):
                result.append(nums[:])
                return
            
            for i in range(start, len(nums)):
                nums[start], nums[i] = nums[i], nums[start]
                backtrack(start + 1)
                nums[start], nums[i] = nums[i], nums[start]
        
        result = []
        backtrack(0)
        return result

public class Solution {
    public IList<IList<int>> Permute(int[] nums) {
        var result = new List<IList<int>>();
        Backtrack(nums, 0, result);
        return result;
    }
    
    private void Backtrack(int[] nums, int start, IList<IList<int>> result) {
        if (start == nums.Length) {
            result.Add(new List<int>(nums));
            return;
        }
        
        for (int i = start; i < nums.Length; i++) {
            Swap(nums, start, i);
            Backtrack(nums, start + 1, result);
            Swap(nums, start, i);
        }
    }
    
    private void Swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function(nums) {
    const result = [];
    
    function backtrack(current) {
        if (current.length === nums.length) {
            result.push([...current]);
            return;
        }
        
        for (let i = 0; i < nums.length; i++) {
            if (current.includes(nums[i])) continue;
            current.push(nums[i]);
            backtrack(current);
            current.pop();
        }
    }
    
    backtrack([]);
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度大小
时间复杂度O(n! × n)
空间复杂度O(n)

说明：

  • 时间复杂度：共有 n! 个排列，每个排列需要 O(n) 的时间复制到结果中
  • 空间复杂度：递归栈深度为 O(n)，不计算结果存储空间

相关题目