算法
以[1,1,2]为例:
[ , , ]
/ | \
/ | \
[1, , ] [ ,1, ] [ , ,1]
/ \ |
/ \ |
[1,1, ] [1, ,1] [ ,1,1]
| | |
[1,1,2] [1,2,1] [2,1,1]
时间复杂度: O(n^n)
总空间复杂度: O(n!)
额外空间复杂度: O(n)
C++代码
class Solution {
public:
static vector<vector<int>> permuteUnique(vector<int> &nums) {
vector<vector<int>> res;
const int n = static_cast<int>(nums.size());
if (nums.empty()) {
return res;
}
sort(nums.begin(), nums.end());
vector<int> path(n);
vector<bool> pathIndexVisited(n);
permuteDfs(nums, 0, path, 0, pathIndexVisited, res);
return res;
}
private:
static void permuteDfs(const vector<int> &nums, const int numIndex,
vector<int> &path, const int pathIndexBegin,
vector<bool> &pathIndexVisited,
vector<vector<int>> &res) {
const int n = static_cast<int>(nums.size());
if (numIndex == n) {
res.push_back(path);
return;
}
for (int pathIndex = pathIndexBegin; pathIndex < n; ++pathIndex) {
if (!pathIndexVisited[pathIndex]) {
pathIndexVisited[pathIndex] = true;
path[pathIndex] = nums[numIndex];
int pathIndexBegin1 = 0;
if (numIndex + 1 < n && nums[numIndex] == nums[numIndex + 1]) {
pathIndexBegin1 = pathIndex + 1;
}
permuteDfs(nums, numIndex + 1, path, pathIndexBegin1, pathIndexVisited,
res);
pathIndexVisited[pathIndex] = false;
}
}
}
};
Java代码
class Solution {
public static List<List<Integer>> permuteUnique(final int[] nums) {
final List<List<Integer>> res = new ArrayList<>();
final int n = nums.length;
if (n == 0) {
return res;
}
Arrays.sort(nums, 0, n);
final int[] path = new int[n];
final boolean[] pathIndexVisited = new boolean[n];
permuteDfs(nums, 0, path, 0, pathIndexVisited, res);
return res;
}
private static void permuteDfs(final int[] nums, final int numIndex,
final int[] path, final int pathIndexBegin,
final boolean[] pathIndexVisited, final List<List<Integer>> res) {
final int n = nums.length;
if (numIndex == n) {
final List<Integer> tmpPath = new ArrayList<>(n);
for (final int num : path) {
tmpPath.add(num);
}
res.add(tmpPath);
return;
}
for (int pathIndex = pathIndexBegin; pathIndex < n; ++pathIndex) {
if (!pathIndexVisited[pathIndex]) {
pathIndexVisited[pathIndex] = true;
path[pathIndex] = nums[numIndex];
final int pathIndexBegin1;
if (numIndex + 1 < n && nums[numIndex] == nums[numIndex + 1]) {
pathIndexBegin1 = pathIndex + 1;
} else {
pathIndexBegin1 = 0;
}
permuteDfs(nums, numIndex + 1, path, pathIndexBegin1, pathIndexVisited, res);
pathIndexVisited[pathIndex] = false;
}
}
}
}
Python3代码
class Solution:
def permuteUnique(self, nums: list) -> list:
self.res = []
if not nums:
return self.res
nums.sort()
self.nums = nums
n = len(nums)
self.path = [-1] * n
self.pathIndexVisited = [False] * n
self.__permuteDfs(0, 0)
return self.res
def __permuteDfs(self, numIndex: int, pathIndexBegin: int) -> None:
n = len(self.nums)
if numIndex == n:
self.res.append(self.path.copy())
return
for pathIndex in range(pathIndexBegin, n):
if not self.pathIndexVisited[pathIndex]:
self.pathIndexVisited[pathIndex] = True
self.path[pathIndex] = self.nums[numIndex]
if numIndex + 1 < n and self.nums[numIndex] == self.nums[numIndex + 1]:
pathIndexBegin1 = pathIndex + 1
else:
pathIndexBegin1 = 0
self.__permuteDfs(numIndex + 1, pathIndexBegin1)
self.pathIndexVisited[pathIndex] = False
Go代码
func permuteUnique(nums []int) [][]int {
var res [][]int
var n int = len(nums)
if n == 0 {
return res
}
sort.Sort(sort.IntSlice(nums))
var path []int = make([]int, n)
var pathIndexVisited []bool = make([]bool, n)
permuteDfs(nums, 0, path, 0, pathIndexVisited, &res)
return res
}
func permuteDfs(nums []int, numIndex int,
path []int, pathIndexBegin int, pathIndexVisited []bool,
res *[][]int) {
var n int = len(nums)
if numIndex == n {
var tmp []int = make([]int, n)
copy(tmp, path)
*res = append(*res, tmp)
return
}
for pathIndex := pathIndexBegin; pathIndex < n; pathIndex++ {
if !pathIndexVisited[pathIndex] {
pathIndexVisited[pathIndex] = true
path[pathIndex] = nums[numIndex]
var pathIndexBegin1 int = 0
if numIndex+1 < n && nums[numIndex] == nums[numIndex+1] {
pathIndexBegin1 = pathIndex + 1
}
permuteDfs(nums, numIndex+1, path, pathIndexBegin1, pathIndexVisited, res)
pathIndexVisited[pathIndex] = false
}
}
}
牛🍺