JAVA练习328- 全排列

题目概览给定一个不含重复数字的数组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] 10nums中的所有整数互不相同来源46. 全排列 - 力扣LeetCode解题分析方法回溯以 [1,2,3] 为例它的排列可以看做先固定 1然后固定 2得到 [1,2,3]然后不固定 2交换 3 和 2 得到 [1,3,2]然后不固定 1交换 1 和 2然后固定 2再固定 1得到 [ 2,1,3]然后不固定 1交换 3 和 1 得到 [2,3,1]然后不固定 2交换 1 和 3然后固定 2再固定 1得到 [ 3,2,1]然后不固定 2交换 2 和 1 得到 [3,1,2]。令当前索引为 i那么这过程就可以看做依次 i 和 [ i, n-1 ] 的数做交换然后递归 i 1继续重复直到遍历 i n得到结果后将 i 和 [ i, n-1 ] 的数交换回来继续遍历最后得到答案。时间复杂度O(n×n!)空间复杂度O(n)class Solution { public ListListInteger permute(int[] nums) { ListInteger list new ArrayList(); for (int num: nums) { list.add(num); } ListListInteger result new ArrayList(); backTracking(nums.length, result, list, 0); return result; } public void backTracking(int n, ListListInteger result, ListInteger nums, int index) { if (index n) { result.add(new ArrayList(nums)); return; } for (int i index; i n; i) { Collections.swap(nums, index, i); backTracking(n, result, nums, index 1); Collections.swap(nums, index, i); } } }