当前位置：首页 > news >正文

力扣经典算法篇-43-全排列(经典回溯问题）

news 2025/8/6 8:29:36

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 中的所有整数互不相同

2、解题

数组的全排列是经典的回溯策略问题。

方法一：（回溯法）

回溯的基本实现步骤要搞清楚。
找到固定不变的量，每趟递归动态变化的量，结果集。
递归就一定要有终止条件，终止条件则呀要添加结果到结果集合中了。
循环递归，注意要先添加元素向前递归，之后进行回退操作；怎么添加的元素进行向后递归，就要怎么删除元素进行回溯。

注意本例要求的元素不能有重复，所以临时动态变量，除了要添加元素的下标，本趟的结果集，还要添加一个set集合用于验证是否重复添加元素。所以在循环递归前，不仅要添加当前元素，还要添加记录下标；在回溯的时候添加的什么，就要删除什么。

代码示例：

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;public class Test49 {public static List<List<Integer>> permute(int[] nums) {// 结果集合List<List<Integer>> result = new ArrayList<>();// 动态变化的临时量// 保存每趟的元素List<Integer> tempList = new ArrayList<>();// 每趟操作需要添加的下标值int index = 0;// 已添加元素的下标值，用于防止重复添加HashSet<Integer> hasSet = new HashSet<>();// 递归（不变的nums，动态tempList,index,hasSet，结果集result）goAndBack(nums, tempList, index, hasSet, result);return result;}private static void goAndBack(int[] nums, List<Integer> tempList, int index, Set<Integer> hasIndex, List<List<Integer>> result) {if (tempList.size() == nums.length) {// 终止条件，本趟元素达到最大元素，注意要新new出来，不然result添加的引用会是同一个。result.add(new ArrayList<>(tempList));return;}// 循环变量for (int i = 0; i < nums.length; i++) {if (!hasIndex.contains(i)) {// 添加元素，记录下标位置hasIndex.add(i);tempList.add(nums[i]);// 向后递归goAndBack(nums, tempList, index + 1, hasIndex, result);// 删除元素，删除下标位置，向前回溯tempList.remove(index);hasIndex.remove(i);}}}public static void main(String[] args) {int[] nums = {1, 2, 3};System.out.println(permute(nums));}
}