当前位置： 面试刷题>> 全排列(经典算法150题)
### 题目描述
**题目：全排列**
给定一个没有重复数字的数组 `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]]
```
### 解题思路
全排列问题可以使用回溯法（backtracking）来解决。回溯法是一种通过穷举所有可能的候选解来找出所有解的算法。如果候选解被确认不是一个解（或者至少不是最后一个解），回溯算法会通过在上一步进行一些变化抛弃该解，即通过在上一步进行一些变化产生新的候选解。
### PHP 代码示例
```php
function permute($nums) {
$result = [];
$visited = array_fill(0, count($nums), false); // 记录数字是否被访问过
backtrack($nums, $visited, [], $result);
return $result;
}
function backtrack($nums, &$visited, $temp, &$result) {
if (count($temp) == count($nums)) {
$result[] = $temp;
return;
}
for ($i = 0; $i < count($nums); $i++) {
if (!$visited[$i]) {
$visited[$i] = true;
$temp[] = $nums[$i];
backtrack($nums, $visited, $temp, $result);
array_pop($temp); // 回溯
$visited[$i] = false;
}
}
}
// 示例用法
$nums = [1, 2, 3];
$result = permute($nums);
print_r($result);
```
### Python 代码示例
```python
def permute(nums):
def backtrack(first=0):
if first == n:
output.append(nums[:])
for i in range(first, n):
nums[first], nums[i] = nums[i], nums[first]
backtrack(first + 1)
nums[first], nums[i] = nums[i], nums[first]
n = len(nums)
output = []
backtrack()
return output
# 示例用法
nums = [1, 2, 3]
print(permute(nums))
```
### JavaScript 代码示例
```javascript
function permute(nums) {
const result = [];
function backtrack(path, used) {
if (path.length === nums.length) {
result.push(path.slice());
return;
}
for (let i = 0; i < nums.length; i++) {
if (!used[i]) {
used[i] = true;
path.push(nums[i]);
backtrack(path, used);
path.pop();
used[i] = false;
}
}
}
const used = new Array(nums.length).fill(false);
backtrack([], used);
return result;
}
// 示例用法
const nums = [1, 2, 3];
console.log(permute(nums));
```
以上代码示例分别用 PHP、Python 和 JavaScript 实现了全排列算法，并给出了示例用法。在实际面试中，可以根据具体需求调整和优化代码。