当前位置： 面试刷题>> 带重复元素的排列 (经典算法题500道)
### 题目描述补充
题目：**带重复元素的排列**
给定一个可能包含重复数字的数组，返回其所有可能的全排列。要求结果中的排列不重复。
**示例 1**:
```
输入: [1,1,2]
输出:
[
[1,1,2],
[1,2,1],
[2,1,1]
]
```
**示例 2**:
```
输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,2,1],
[3,1,2]
]
```
### 解题思路
对于带重复元素的排列问题，我们可以使用回溯法来解决，但需要注意在回溯过程中跳过重复的排列。这通常通过在递归调用之前和之后对数组进行排序，并在递归过程中跳过与前一个元素相同的元素来实现。
### PHP 示例代码
```php
function permuteUnique($nums) {
sort($nums); // 先排序，以便后续跳过重复元素
$result = [];
backtrack($nums, [], $result);
return $result;
}
function backtrack(&$nums, $temp, &$result) {
if (count($temp) == count($nums)) {
$result[] = $temp;
return;
}
for ($i = 0; $i < count($nums); $i++) {
// 跳过重复元素
if ($i > 0 && $nums[$i] == $nums[$i - 1] && in_array($nums[$i], $temp)) {
continue;
}
$temp[] = $nums[$i];
backtrack($nums, $temp, $result);
array_pop($temp);
}
}
// 示例用法
$nums = [1, 1, 2];
$result = permuteUnique($nums);
print_r($result);
```
### Python 示例代码
```python
def permuteUnique(nums):
def backtrack(first=0):
if first == n:
output.append(nums[:])
for i in range(first, n):
# 确保不选择重复的元素
if i > first and nums[i] == nums[i-1]:
continue
nums[first], nums[i] = nums[i], nums[first]
backtrack(first + 1)
nums[first], nums[i] = nums[i], nums[first]
nums.sort()
n = len(nums)
output = []
backtrack()
return output
# 示例用法
nums = [1, 1, 2]
result = permuteUnique(nums)
print(result)
```
### JavaScript 示例代码
```javascript
function permuteUnique(nums) {
nums.sort((a, b) => a - b);
const result = [];
const backtrack = (first = 0) => {
if (first === nums.length) {
result.push([...nums]);
return;
}
for (let i = first; i < nums.length; i++) {
if (i > first && nums[i] === nums[i - 1]) continue; // 跳过重复
[nums[first], nums[i]] = [nums[i], nums[first]];
backtrack(first + 1);
[nums[first], nums[i]] = [nums[i], nums[first]];
}
};
backtrack();
return result;
}
// 示例用法
const nums = [1, 1, 2];
const result = permuteUnique(nums);
console.log(result);
```
**码小课网站中有更多相关内容分享给大家学习**，包括但不限于算法题解、数据结构、面试技巧等，欢迎访问码小课网站获取更多学习资源。