46. 全排列

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

示例：

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

回溯

想法是$nums.length$长度的排列排着固定每一位，每个位置都可以放置从当前位置开始到最后的数字中的一个（因为不重复），因此循环每次从$start$到最后中选择一个换到当前的固定位，然后将其加入$path$直到长度达到$nums.length$之后，将这个答案添加到结果数组中。回溯就在于递归下一次返回后，将所有操作回溯到这次变化之前：

import java.util.ArrayList;
import java.util.List;class Solution {List<Integer> path = new ArrayList<>();List<List<Integer>> res = new ArrayList<>();public void swap (int[] nums, int i, int j) {int temp = nums[i];nums[i] = nums[j];nums[j] = temp;}public void backtrack(int[] nums, int start) {if(start >= nums.length) {res.add(new ArrayList<>(path));return;}for (int i = start; i < nums.length; i++) {swap(nums, start, i);   //选择一个放到固定位path.add(nums[start]);backtrack(nums, start + 1); //递归path.remove(path.size() - 1);   //回溯复原swap(nums, start, i);}}public List<List<Integer>> permute(int[] nums) {backtrack(nums, 0);return res;}
}

复杂度分析

• 时间复杂度：$O(n!)$

  每个固定位的选择从$n,n-1,...,1$因此为$O(n\times n-1\times ...\times 1)=O(n!)$。

• 空间复杂度：$O(n)$

  栈的递归深度最多为排列长度$n$。