本文共 2058 字，大约阅读时间需要 6 分钟。

全排列生成问题分析与解决方案

问题描述

给定一个没有重复数字的序列，要求返回其所有可能的全排列。

示例

输入：[1,2,3]

输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

思路分析

生成全排列的方法有多种，这里使用交换元素的方法来实现。具体来说，可以通过递归的方式，在每个位置上交换当前元素与后续元素，从而生成所有可能的排列。为了避免重复，我们需要在递归回溯时恢复交换前的元素位置。

代码实现

以下是两种方法的实现代码：

自写代码：

import java.util.ArrayList;import java.util.List;import java.util.Scanner;public class Solution {    List
   
     res = new ArrayList<>();    public List
    
      permute(int[] nums) {        solve(nums, 0);        return res;    }    private void solve(int[] nums, int k) {        if (k == nums.length) {            List
     
       list = new ArrayList<>();            for (int i = 0; i < nums.length; ++i) {                list.add(nums[i]);            }            res.add(list);            return;        }        for (int i = k; i < nums.length; ++i) {            int t = nums[i];            nums[i] = nums[k];            nums[k] = t;            solve(nums, k + 1);            // 回溯            t = nums[i];            nums[i] = nums[k];            nums[k] = t;        }    }}
     
    
   

官方代码：

import java.util.*;public class Solution {    public void backtrack(int n, ArrayList
   
     nums, List
    
      output, int first) {        if (first == n) {            output.add(new ArrayList
     
      (nums));        }        for (int i = first; i < n; ++i) {            Collections.swap(nums, first, i);            backtrack(n, nums, output, first + 1);            Collections.swap(nums, first, i);        }    }    public List
      
        permute(int[] nums) {        List
       
         output = new LinkedList<>();        ArrayList
        
          nums_lst = new ArrayList<>(); for (int num : nums) { nums_lst.add(num); } int n = nums.length; backtrack(n, nums_lst, output, 0); return output; }}
        
       
      
     
    
   

总结

通过上述方法，我们可以轻松地生成一个没有重复数字的序列的所有全排列。两种方法都利用了递归和交换元素的思想，确保了生成的全排列是唯一且完整的。选择哪种方法取决于具体的性能需求和代码风格偏好。