LeetCode 46 全排列

题目描述

全排列

给定一个不含重复数字的数组 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 中的所有整数 互不相同

解法

回溯法

这个问题可以看作有 n 个排列成一行的空格，我们需要从左往右依此填入题目给定的 n 个数，每个数只能使用一次。那么很直接的可以想到一种穷举的算法，即从左往右每一个位置都依此尝试填入一个数，看能不能填完这 n 个空格，在程序中我们可以用「回溯法」来模拟这个过程。

定义回溯函数：

private void backtrack(int n, List<Integer> output, ArrayList<List<Integer>> res, int first) {
}

first为当前要填的位置，n位需要填的总位置数。

• 如果 first=n，说明已经填完了 n 个位置（注意下标从 0 开始），找到了一个可行的解，将 output 放入答案数组中，递归结束。
• 如果first < n，填第 first 个数的时候遍历题目给定的 n 个数，如果这个数没有被标记过，就尝试填入，并将其标记，继续尝试填下一个位置。
• 假设我们已经填到第 first 个位置，那么 nums 数组中 [0,first−1]是已填过的数的集合，[first,n−1] 是待填的数的集合。

java代码：

class Solution {/*** 回溯** @param nums* @return*/public List<List<Integer>> permute(int[] nums) {ArrayList<List<Integer>> res = new ArrayList<>();// nums不好交换位置，使用ListList<Integer> output = new ArrayList<Integer>();for (int num : nums) {output.add(num);}int n = nums.length;// 使用回溯backtrack(n, output, res, 0);return res;}/*** 回溯算法：*  如果 first=n，说明已经填完了 n 个位置（注意下标从 0 开始），找到了一个可行的解，将 output 放入答案数组中，递归结束。*  如果first < n，填第 first 个数的时候遍历题目给定的 n 个数，如果这个数没有被标记过，就尝试填入，并将其标记，继续尝试填下一个位置*  假设我们已经填到第 first 个位置，那么 nums 数组中 [0,first−1]是已填过的数的集合，[first,n−1] 是待填的数的集合*** @param n  原数组长度，也是结果数组最后的总长度* @param output  当前的数组* @param res  结果数组* @param first  当前位置*/private void backtrack(int n, List<Integer> output, ArrayList<List<Integer>> res, int first) {// 已经填完了 n 个位置，将 output 放入答案数组中，递归结束if (first == n) {// 注意这里的output，每次递归是公用的，所以需要把它放入新列表再放到结果列表res.add(new ArrayList<>(output));}// 开始填第first个数for (int i = first; i < n; i++) {// 动态维护数组，交换位置Collections.swap(output, first, i);// 继续递归填下一个数backtrack(n, output, res, first + 1);// 回退，需要吧位置交换回来Collections.swap(output, first, i);}}
}

复杂度

• 时间复杂度：O(n*n!)，其中 n 为数组的长度
• 空间复杂度：O(n)。