# 0046. 全排列

## 题目地址(46. 全排列)

<https://leetcode-cn.com/problems/permutations/>

## 题目描述

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

示例:

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

## 前置知识

* [回溯](https://github.com/azl397985856/leetcode/blob/master/thinkings/backtrack.md)

## 公司

* 阿里
* 腾讯
* 百度
* 字节

## 思路

回溯的基本思路清参考上方的回溯专题。

以 \[1,2,3] 为例，我们的逻辑是：

* 先从 \[1,2,3] 选取一个数。
* 然后继续从 \[1,2,3] 选取一个数，并且这个数不能是已经选取过的数。

> 如何确保这个数不能是已经选取过的数？我们可以直接在已经选取的数字中线性查找，也可以将已经选取的数字中放到 hashset 中，这样就可以在 $O(1)$ 的时间来判断是否已经被选取了，只不过需要额外的空间。

* 重复这个过程直到选取的数字个数达到了 3。

## 关键点解析

* 回溯法
* backtrack 解题公式

## 代码

* 语言支持: Javascript, Python3,CPP

Javascript Code:

```javascript
function backtrack(list, tempList, nums) {
  if (tempList.length === nums.length) return list.push([...tempList]);
  for (let i = 0; i < nums.length; i++) {
    if (tempList.includes(nums[i])) continue;
    tempList.push(nums[i]);
    backtrack(list, tempList, nums);
    tempList.pop();
  }
}
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function (nums) {
  const list = [];
  backtrack(list, [], nums);
  return list;
};
```

Python3 Code:

```python
class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        """itertools库内置了这个函数"""
        import itertools
        return itertools.permutations(nums)

    def permute2(self, nums: List[int]) -> List[List[int]]:
        """自己写回溯法"""
        res = []
        def backtrack(nums, pre_list):
            if len(nums) <= 0:
                res.append(pre_list)
            else:
                for i in nums:
                    # 注意copy一份新的调用，否则无法正常循环
                    p_list = pre_list.copy()
                    p_list.append(i)
                    left_nums = nums.copy()
                    left_nums.remove(i)
                    backtrack(left_nums, p_list)
        backtrack(nums, [])
        return res

    def permute3(self, nums: List[int]) -> List[List[int]]:
        """回溯的另一种写法"""
        res = []
        length = len(nums)
        def backtrack(start=0):
            if start == length:
                # nums[:] 返回 nums 的一个副本，指向新的引用，这样后续的操作不会影响已经已知解
                res.append(nums[:])
            for i in range(start, length):
                nums[start], nums[i] = nums[i], nums[start]
                backtrack(start+1)
                nums[start], nums[i] = nums[i], nums[start]
        backtrack()
        return res
```

CPP Code:

```cpp
class Solution {
    vector<vector<int>> ans;
    void dfs(vector<int> &nums, int start) {
        if (start == nums.size() - 1) {
            ans.push_back(nums);
            return;
        }
        for (int i = start; i < nums.size(); ++i) {
            swap(nums[i], nums[start]);
            dfs(nums, start + 1);
            swap(nums[i], nums[start]);
        }
    }
public:
    vector<vector<int>> permute(vector<int>& nums) {
        dfs(nums, 0);
        return ans;
    }
};
```

**复杂度分析** 令 N 为数组长度。

* 时间复杂度：$O(N!)$
* 空间复杂度：$O(N)$

## 相关题目

* [31.next-permutation](/leetcode-solution/medium/31.next-permutation.md)
* [39.combination-sum](/leetcode-solution/medium/39.combination-sum.md)
* [40.combination-sum-ii](/leetcode-solution/medium/40.combination-sum-ii.md)
* [47.permutations-ii](/leetcode-solution/medium/47.permutations-ii.md)
* [60.permutation-sequence](/leetcode-solution/medium/60.permutation-sequence.md)
* [78.subsets](/leetcode-solution/medium/78.subsets.md)
* [90.subsets-ii](/leetcode-solution/medium/90.subsets-ii.md)
* [113.path-sum-ii](/leetcode-solution/medium/113.path-sum-ii.md)
* [131.palindrome-partitioning](/leetcode-solution/medium/131.palindrome-partitioning.md)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/46.permutations.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.