【CT】LeetCode手撕—46. 全排列

2024-06-19 10:28

文章标签 leetcode 排列 46 ct

本文主要是介绍【CT】LeetCode手撕—46. 全排列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

原题连接：46. 全排列

1- 思路

模式识别

模式1：不含重复数字的数组 nums ——> 任意顺序可能的全排列 ——> 回溯
模式2：全排列 ——> 排列问题，不同于组合问题 ——>
回溯每次相当于枚举一个结果集，当当层结果集的长度为 nums.length 时候收集结果

为什么排列问题需要用 used 数组？

排列问题关注元素的顺序，即[1, 2]和[2, 1]被视为两个不同的排列。为了生成所有可能的排列，每个元素在每个特定的排列中只能出现一次，但可以在不同的排列中重复出现。
used数组的作用：在排列问题中，used数组用来跟踪每个元素是否已经被当前排列使用。这是因为每个元素在生成单个排列时只能使用一次，但在生成不同的排列时可以重新使用。used数组确保在构建每个排列时，每个元素只被选择一次。

组合问题中

组合问题不关注元素的顺序，即[1, 2]和[2, 1]被视为相同的组合。组合问题通常要求选择一个子集，不考虑元素的排列顺序。
组合问题中的递归调用：在组合问题中，通常不需要used数组，因为一旦选择了一个元素，就不需要再次选择它。递归调用时，通常将下一个元素的索引传递给递归函数，这样就自然地避免了重复使用同一个元素。
组合问题通过传递 startIndex 来避免递归过程中重复取元素的问题。

回溯三部曲

1.回溯参数返回值
- 参数为：参数 nums
- 返回值为 void，通过定义 List<List<Integer>> res 收集结果
2.终止条件 && 结果收集
- 当当前 iterm.size() == nums.length 收集结果并 return;
3.回溯搜索的遍历过程
- for(int i = 0; i<nums.length;i++)

2- 实现

⭐46. 全排列——题解思路

在这里插入图片描述

class Solution {List<List<Integer>> res = new ArrayList<>();List<Integer> path = new ArrayList<>();boolean[] used;public List<List<Integer>> permute(int[] nums) {used = new boolean[nums.length];Arrays.fill(used,false);backTracing(nums);return res;}public void backTracing(int[] nums){// 1.终止条件if(path.size() == nums.length){res.add(new ArrayList(path));return ;}// 2. 回溯for(int i = 0 ; i < nums.length ;i++){if(used[i]){continue;}used[i] = true;path.add(nums[i]);backTracing(nums);used[i] = false;path.removeLast();}}
}

3- ACM实现

public class permute {static List<List<Integer>> res = new ArrayList<>();static List<Integer> path = new ArrayList<>();static boolean[] used;public static List<List<Integer>> permuteFunction(int[] nums){used = new boolean[nums.length];Arrays.fill(used,false);backTracing(nums);return res;}public static void backTracing(int[] nums){// 2.终止条件if(nums.length==path.size()){res.add(new ArrayList<>(path));}// 3.回溯遍历搜索过程for(int i = 0; i < nums.length;i++){if(used[i]){continue;}used[i] = true;path.add(nums[i]);backTracing(nums);used[i] = false;path.remove(path.size()-1);}}public static void main(String[] args) {Scanner sc = new Scanner(System.in);System.out.println("输入全排列数组长度");int n = sc.nextInt();System.out.println("输入数组值");int[] nums = new int[n];for(int i = 0 ; i < n;i++){nums[i] = sc.nextInt();}System.out.println("全排列的结果是");List<List<Integer>> forRes = permuteFunction(nums);System.out.println(forRes.toString());}
}