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] <= 10
• nums中的所有整数互不相同

来源：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 List<List<Integer>> permute(int[] nums) { List<Integer> list = new ArrayList<>(); for (int num: nums) { list.add(num); } List<List<Integer>> result = new ArrayList<>(); backTracking(nums.length, result, list, 0); return result; } public void backTracking(int n, List<List<Integer>> result, List<Integer> 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); } } }