全排列

题目链接描述示例初始代码模板代码

题目链接

https://leetcode-cn.com/problems/permutations/

描述

给定一个 没有重复 数字的序列，返回其所有可能的全排列。

示例

输入: [1,2,3] 输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]

初始代码模板

class Solution { public List<List<Integer>> permute(int[] nums) { } }

代码

回溯参考模板

backtrack () 终止条件 for 选择 in 选择列表 条件 选择 backtrack 撤销选择

首先根据参考模板先写出一个可以用的代码，不一定是最优，但是要先保证逻辑正确。

根据题目给定条件，寻找全排列的组合，终止条件应该就是寻找到一个组合的情况，也就是寻找过的长度等于给定的数组长度；给定的数组即为选择列表，条件为未曾被选择的数字，然后把满足的数字加入，调用函数后撤销选择就好。

详细看代码吧，写的有点模糊。

class Solution { List<List<Integer>> ans = new LinkedList<>(); //标识哪些数字被选，哪些没有 boolean[] used; public List<List<Integer>> permute(int[] nums) { used = new boolean[nums.length]; backtrack(new LinkedList<Integer>(), nums); return ans; } //list保存当前的组合，nums为选择列表 private void backtrack(LinkedList<Integer> list, int[] nums) { //如果当前已经寻找的组合的长度等于nums长度，说明已经找到了一个答案 if (list.size() == nums.length) { ans.add(new LinkedList<>(list)); return; } //整个nums是一个选择列表 for (int i = 0; i < nums.length; i++) { //选择这个数的条件是这个数还没有被选过，通过used辨识 if (!used[i]) { //加入到当前的组合中 list.add(nums[i]); //在调用函数前把当前的数标识改为已经选择过，避免重复选择 used[i] = true; //保留本次的情况，进行进一步的寻找 backtrack(list, nums); //返回到未被选择的情况，“时间回溯” used[i] = false; list.removeLast(); } } } }

解题思路没有问题，但是效率有些低，继续优化。 发现在 for 选择 in 选择列表 中存在很多无效的遍历，在数据大时尤其如此，设法减少选择列表 以下代码可作为参考，整体思路差不多，只是选择策略上有所调整

class Solution { List<List<Integer>> ans = new LinkedList<>(); public List<List<Integer>> permute(int[] nums) { backtrack(nums, 0); return ans; } private void backtrack(int[] nums, int index) { if (index == nums.length) { List<Integer> list = new LinkedList<>(); for (Integer i : nums) { list.add(i); } ans.add(list); return; } for (int i = index; i < nums.length; i++) { swap(nums, index, i); backtrack(nums, index + 1); swap(nums, index, i); } } private void swap(int[] nums, int index1, int index2) { int temp = nums[index1]; nums[index1] = nums[index2]; nums[index2] = temp; } }