本文共 1858 字，大约阅读时间需要 6 分钟。
问题描述
int[] nums数组，数组中没有重复的数字，求这些数字能够组成的所有排列。
例如：
输入：[2,5,3]输出：[[2,5,3],[2,3,5],[5,2,3],[5,3,2],[3,2,5],[3,5,2]]
题目来源：力扣（LeetCode） 链接： https:// leetcode-cn.com/problem s/permutations
问题分析
全排列，经典的数学问题。像问题描述中的这个例子，我们自己也能心算出来，甚至就算输入的是4个数，我们也能拿笔纸算出来。但是，如果输入的数组中的整数个数，达到5个、6个，甚至是100个的时候，你还能用笔算出来吗，就算能算出来，也得耗费大量的时间，还担心出错。而计算机程序解决此类问题，有得天独厚的优势，它计算速度快、结果精确，擅长做递归调用。好，面对这个问题，首先我们就要将它分解，分解得足够小，小到只是初始条件不同，而执行的动作完全是一样的地步，便于计算机执行。
对于一个排列来说，它的最小单元，就是它的一个位置上的取值，例如[2,5,3]，它有3个位置用来放置3个数据，所以它有3个单元，每个单元有什么不同呢，假如第一个位置上放了5，那么第2个位置，就只能放2和3了，很显然，每个单元放置数据时面对的可选数据不同，但执行的动作是一样，就是把符合条件的数据放到对应的位置。java程序中，循环结构，恰好就能够作为当前问题的一个最小单元，循环条件就是该位置所能放置的所有取值，循环体内部，我们用一个列表将当前的临时排列存储起来，并将当前的数值标记为已使用，接着进入下一个位置的放置操作，对应程序就是递归调用，调用完毕后，再将当前数值标记为未使用，为当前位置取下一个有效值作准备，s当临时列表的长度，等于初始输入数组的长度时，我们就得到了其中的一个排列，将其放置到结果列表中，当程序运行完，结果列表就是我们需要的全排列。
代码实现
@Testpublic void testPermute() { int[] nums={ 1, 0, 3}; new Solution().permute(nums);}class Solution { private List > result= new LinkedList<>(); private int length; private int[] arr; private boolean[] visit; public List > permute(int[] nums) { if (nums == null || nums.length == 0) { return Collections.emptyList(); } length = nums.length; arr = nums; //用来记录数组中某个值是否已被使用visit = new boolean[length]; generate(new LinkedList ()); System.out.println("result: " + result); return result; } private void generate(List temp) { //得到了其中一个排列if (temp.size() == length) { result.add(new LinkedList (temp)); return; } //每个位置，都有权利取遍所有值for (int i = 0; i < arr.length; i++) { //前提是这个值没有被别的位置使用if (!visit[i]) { temp.add(arr[i]); visit[i] = true; //递归，进入下一个位置generate(temp); //回溯，重新安排当前位置取值temp.remove(temp.size() - 1); visit[i] = false; } } }}
转载地址：https://blog.csdn.net/weixin_34759094/article/details/112631236 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！
发表评论
最新留言
关于作者
