给定一个数字列表，返回其所有可能的排列。

在线评测地址

样例 1：

输入：[1] 输出： [   [1] ] 

样例 2：

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

算法：DFS （回溯法）

算法分析

对于全排列，比如[1,2,3]的全排列，我们按顺序穷举，步骤如下：1. 首先会固定第一位为 1，然后第二位如果取 2，最后一位只能是 3 ；再可以把第二位变成 3，第三位就只能是 2 ； 2. 接下来变化第一位变成 2，然后再像上述的过程穷举后两位分别是 1,3 ； 3. 最后第一位是 3，再穷举后两位分别是 1,2，整个过程就完成了。 以上的过程，很适合使用 DFS （回溯法）进行实现。

算法步骤

1. 根据题目要求，首先需要定义并初始化一个布尔类型 used 数组记录每个数字是否已被使用，一个数组 current 记录当前遍历的排列，一个二维数组 results 记录所有结果；
2. 对输入的数字列表 nums 进行深度优先搜索，传入的参数包括：数字列表 nums 、used 、current 、results ；

• 边界条件：当 current 中的元素个数和 nums 的相同，代表一次遍历完毕，将当前的 current 加入 results 并 return ；
• 遍历 nums，如果 nums 中当前这个元素未被使用，则在 used 中标记其已使用，将其加入 current，并递归调用 dfs ；
• 调用完毕后需要回退，即在 used 中标记其未使用；

复杂度

• 时间复杂度：

• 对于每一位，可以从 n 个元素中选择 k 个来放置，共有 n 位。
• 空间复杂度：O(N!)
  • 共有 N!个全排列，故需要保存 N!个解

import java.util.ArrayList;import java.util.List; public class Solution {     /*      * @param nums: A list of integers.      *       * @return: A list of permutations.      */     public List<List<Integer>> permute(int[] nums) {         List<List<Integer>> results = new ArrayList<>();          // 如果数组为空直接返回空         if (nums == null) {             return results;         }          //dfs         dfs(nums, new boolean[nums.length], new ArrayList<Integer>(), results);          return results;     }      private void dfs(int[] nums, boolean[] used, List<Integer> current, List<List<Integer>> results) {                  //找到一组排列，已到达边界条件         if (nums.length == current.size()) {             results.add(new ArrayList<Integer>(current));             return;         }          for (int i = 0; i < nums.length; i++) {             //i 位置这个元素已经被用过             if (used[i]) {                 continue;             }              //继续递归             current.add(nums[i]);             used[i] = true;             dfs(nums, used, current, results);             used[i] = false;             current.remove(current.size() - 1);         }     } } 

大佬有話說 (0)