后端开发刷题 | 没有重复项数字的全排列

描述

给出一组数字，返回该组数字的所有排列

例如：

[1,2,3]的所有排列如下
[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2], [3,2,1].
（以数字在数组中的位置靠前为优先级，按字典序排列输出。）

数据范围：数字个数 0<n≤6

要求：空间复杂度 O(n!)，时间复杂度 O(n!）

示例1

输入：

[1,2,3]

返回值：

[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例2

输入：

[1]

返回值：

[[1]]

思路分析：

经典的回溯算法问题——全排列（Permutations）

• permute 方法：这是类的公共方法，接收一个整数数组 num 作为输入，并返回一个 ArrayList<ArrayList<Integer>> 类型的列表，其中每个内部列表代表 num 数组的一个排列。

  • 初始化一个 ArrayList<ArrayList<Integer>> 类型的 result 列表，用于存储所有排列。
  • 初始化一个 LinkedList<Integer> 类型的 list，用于在回溯过程中构建当前的排列。
  • 调用 backTrack 方法开始回溯过程。

• backTrack 方法：这是一个私有方法，用于递归地生成所有排列。它接收三个参数：

  • num：原始整数数组。

  • list：当前正在构建的排列（以链表形式）。

  • result：用于存储所有排列的列表。

  • 递归终止条件：如果 list 的大小等于 num 的长度，说明已经构建了一个完整的排列，此时将这个排列（通过 new ArrayList<Integer>(list) 转换为不可变列表）添加到 result 中，并返回。

  • 递归过程：遍历 num 数组中的每个元素，如果当前元素已经存在于 list 中，则跳过该元素（避免重复排列）。否则，将该元素添加到 list 中，并递归调用 backTrack 方法继续构建下一个元素。递归返回后，需要撤销上一步的选择（即移除 list 中最后添加的元素），以便尝试其他可能的排列。

代码：

import java.util.*;public class Solution {public ArrayList<ArrayList<Integer>> permute(int[] num) {ArrayList<ArrayList<Integer>> result = new ArrayList<>();LinkedList<Integer> list = new LinkedList<>();backTrack(num, list, result);return result;}private void backTrack(int[] num, LinkedList<Integer> list,ArrayList<ArrayList<Integer>> result) {if (list.size() == num.length) {result.add(new ArrayList<Integer>(list));return;}for (int i = 0; i < num.length; i++) {if (list.contains(num[i])) {continue;}list.add(num[i]);backTrack(num, list, result);list.removeLast();}}
}