【LetMeFly】47.全排列 II：内置函数 / 回溯（长篇小论）
力扣题目链接：https://leetcode.cn/problems/permutations-ii/
给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
示例 1：
输入：nums = [1,1,2]
输出：
[[1,1,2],
[1,2,1],
[2,1,1]]
示例 2：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
提示：
1 <= nums.length <= 8-10 <= nums[i] <= 10
解题方法一：使用内置函数
解题思路
C++和Python都有全排列的内置函数，C++直接不生成重复的，Python去个重即可。
直接使用库函数不香么？
时空复杂度分析
- 时间复杂度$O(n!)$，其中$n=len(nums)$
- 空间复杂度：C++$O(\log n)$，Python$O(n!)$
其中C++单次调用next_permutation时间复杂度最坏$O(n)$，$n$个数的全排列最多$n!$种，$O(n\times n!) = O((n + 1)\times n!) = O((n + 1)!) = O(n!)$。
C++单次调用next_permutation的空间复杂度为$O(1)$，返回值不计入力扣空间复杂度。1, 2
Python需要set等额外的中间变量来存放所有结果。
AC代码
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
class Solution {
public:
vector<vector<int>> permuteUnique(vector<int>& nums) {
vector<vector<int>> ans;
sort(nums.begin(), nums.end());
do {
ans.push_back(nums);
} while (next_permutation(nums.begin(), nums.end()));
return ans;
}
};
|
Python
1
2
3
4
5
6
7
8
9
10
11
12
| '''
Author: LetMeFly
Date: 2025-02-06 13:55:07
LastEditors: LetMeFly.xyz
LastEditTime: 2025-02-06 13:56:30
'''
from typing import List
from itertools import permutations
class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
return list(set(permutations(nums)))
|
解题方法二：回溯
解题思路
首先将nums数组排个序，使用一个数组记录哪个元素被选过，然后开始深搜回溯。
首先如果已选元素个数达到了$n$个，则说明生成了一种全排列方案，加入答案数组并返回。
否则开始遍历nums数组：
- 如果当前元素被选过，或者当前元素和上一个元素相同且上一个元素没被选，则
continue。（防止重复选择或重复方案）
- 否则，选择当前元素并标记，递归，递归结束后移除当前元素并取消标记
时空复杂度分析
- 时间复杂度$O(n!)$，其中$n=len(nums)$
- 空间复杂度：C++$O(n)$
AC代码
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
#ifdef _WIN32
#include "_[1,2]toVector.h"
#endif
class Solution {
private:
void dfs(int n, vector<vector<int>>& ans, vector<int>& now, vector<bool>& visited, vector<int>& nums) {
if (n == nums.size()) {
ans.push_back(now);
}
for (int i = 0; i < nums.size(); i++) {
if (visited[i] || i && nums[i] == nums[i - 1] && !visited[i - 1]) {
continue;
}
now.push_back(nums[i]);
visited[i] = true;
dfs(n + 1, ans, now, visited, nums);
visited[i] = false;
now.pop_back();
}
}
public:
vector<vector<int>> permuteUnique(vector<int>& nums) {
vector<vector<int>> ans;
vector<int> now;
vector<bool> visited(nums.size());
sort(nums.begin(), nums.end());
dfs(0, ans, now, visited, nums);
return ans;
}
};
|
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| '''
Author: LetMeFly
Date: 2025-02-06 13:57:31
LastEditors: LetMeFly.xyz
LastEditTime: 2025-02-06 14:07:13
'''
from typing import List
class Solution:
def dfs(self, n: int) -> None:
if n == len(self.nums):
self.ans.append([i for i in self.now])
return
for i in range(len(self.nums)):
if self.visited[i] or i and self.nums[i] == self.nums[i - 1] and not self.visited[i - 1]:
continue
self.now.append(self.nums[i])
self.visited[i] = True
self.dfs(n + 1)
self.visited[i] = False
self.now.pop()
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
self.nums = sorted(nums)
self.ans: List[List[int]] = []
self.now: List[int] = []
self.visited = [False] * len(nums)
self.dfs(0)
return self.ans
|
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
|
import java.util.Arrays;
import java.util.ArrayList;
import java.util.List;
class Solution {
private List<List<Integer>> ans = new ArrayList<>();
private List<Integer> now = new ArrayList<>();
private int[] nums;
private boolean[] visited;
private void dfs(int n) {
if (n == nums.length) {
ans.add(new ArrayList<Integer>(now));
return;
}
for (int i = 0; i < nums.length; i++) {
if (visited[i] || i > 0 && nums[i] == nums[i - 1] && !visited[i - 1]) {
continue;
}
now.add(nums[i]);
visited[i] = true;
dfs(n + 1);
visited[i] = false;
now.remove(now.size() - 1);
}
}
public List<List<Integer>> permuteUnique(int[] nums) {
Arrays.sort(nums);
this.nums = nums;
visited = new boolean[nums.length];
dfs(0);
return ans;
}
}
|
Go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
package main
import "sort"
func dfs_P2(n int, ans *[][]int, now []int, visited []bool, nums []int) {
if n == len(nums) {
*ans = append(*ans, append(make([]int, 0), now...))
return
}
for i := range nums {
if visited[i] || i > 0 && nums[i] == nums[i - 1] && !visited[i - 1] {
continue
}
now = append(now, nums[i])
visited[i] = true
dfs_P2(n + 1, ans, now, visited, nums)
visited[i] = false
now = now[:len(now) - 1]
}
}
func permuteUnique(nums []int) (ans [][]int) {
sort.Ints(nums)
var now []int
visited := make([]bool, len(nums))
dfs_P2(0, &ans, now, visited, nums)
return ans;
}
|
End
同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/145473834