回溯算法解决全排列问题

1. 问题描述

定义：给定一个不含重复数字的数组 nums ，返回其所有可能的全排列。

示例：
输入数组 [1, 2, 3]
输出结果应该为：
在这里插入图片描述

leetcode 地址

2. 代码实现

package com.ztq.algorithm.BackTrack;import java.util.List;
import java.util.ArrayList;
import java.util.ListIterator;/*** @author: ZTQ* @Title: FullRange* @ProjectName: algo* @Description: 全排列问题* @date: 2024/12/4 12:12*/
public class FullRange {public static void main(String[] args) {int[] arr = {1, 2, 3, 4};List<List<Integer>> permute = permute(arr);int num = 0;for (List<Integer> list : permute) {System.out.println(list.toString());num += 1;}System.out.println("共计 " + num + " 种");System.out.println("正确答案为 " + getFactorial(arr.length));}/*** 求一个数字的阶乘** @param num 要求的数字* @return*/public static int getFactorial(int num) {int result = 1;for (int i = num; i >= 1; i--) {result *= i;}return result;}/*** 调用辅助的回溯方法生成所有的全排列** @param nums 整数数组* @return 结果列表*/public static List<List<Integer>> permute(int[] nums) {List<List<Integer>> result = new ArrayList<>(); // 用于存储结果boolean[] visited = new boolean[nums.length]; // 记录当前数字是否被使用// 调用回溯方法backtrack(nums, new ArrayList<>(), visited, result);return result;}/*** @param nums* @param path* @param visited* @param result*/private static void backtrack(int[] nums, List<Integer> path, boolean[] visited, List<List<Integer>> result) {// 递归终止条件：路径长度等于输入数组长度// 当 path 的长度等于 nums 数组的长度时，表明已经生成了一个完整的排列，将其加入 result。/*通过 new ArrayList<>(path) 创建一个 深拷贝（副本），可以避免引用共享的问题。new ArrayList<>(path) 的作用：创建一个包含当前 path 内容的新对象，独立于原始的 path。后续修改 path 不会影响存储在 result 中的内容。*/if (path.size() == nums.length) {// 将当前路径复制一份，存入结果列表List<Integer> completedPath = new ArrayList<>(path);result.add(completedPath);return; // 回溯终止条件，退出递归}// 遍历数字数组，尝试选择每个数字// 遍历输入数组 nums，每次选择一个未使用的数字加入当前路径 path。// 通过 visited 数组标记已选择的数字。for (int i = 0; i < nums.length; i++) {if (visited[i]) {continue; // 如果当前数字已经被使用，跳过}// 做出选择：将数字加入路径并标记为已使用path.add(nums[i]);visited[i] = true;// 递归调用，进入下一层决策树backtrack(nums, path, visited, result);// 撤销选择：从路径中移除最后加入的数字，并取消标记// 回溯后撤销选择，即从路径 path 中移除当前数字，// 并将 visited[i] 重置为 false，以便其他递归分支可以使用该数字。// 从路径中移除最后加入的数字，恢复路径到上一个状态。path.remove(path.size() - 1);visited[i] = false;}}
}