47. 全排列 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

分析：

• 面对这道算法题目，二当家的陷入了沉思。
• 要做全排列，回溯是大方向。
• 有重复的数字，又要不重复的排列，去重是必须的了。
• 要求是对排列去重，但是也可以理解为回溯时，跳过已经“尝试”过的数字。
• 如果数字很多，可以考虑计数排序法，这里顺序不重要，重要的是快速去重。
• 但是提示里说数字最多8个，那直接排序，同样顺序不重要，只是为了相同的数字挨在一起，每次回溯跳过相同数字即可。

题解：

rust

impl Solution {pub fn permute_unique(mut nums: Vec<i32>) -> Vec<Vec<i32>> {fn backtrack(nums: &Vec<i32>, ans: &mut Vec<Vec<i32>>, vis: &mut Vec<bool>, row: &mut Vec<i32>) {if row.len() == nums.len() {ans.push(row.clone());return;}nums.iter().enumerate().for_each(|(i, v)| {if !vis[i] && (i == 0 || nums[i] != nums[i - 1] || vis[i - 1]) {row.push(nums[i]);vis[i] = true;backtrack(nums, ans, vis, row);row.pop();vis[i] = false;}});}let mut ans = Vec::new();nums.sort();let mut vis = vec![false; nums.len()];let mut row = Vec::new();backtrack(&mut nums, &mut ans, &mut vis, &mut row);return ans;}
}

go

func permuteUnique(nums []int) (ans [][]int) {var backtrack func([]bool, []int)backtrack = func(vis []bool, row []int) {if len(row) == len(nums) {ans = append(ans, append([]int(nil), row...))return}for i, v := range nums {if vis[i] || i > 0 && !vis[i-1] && v == nums[i-1] {continue}row = append(row, v)vis[i] = truebacktrack(vis, row)row = row[:len(row)-1]vis[i] = false}}sort.Ints(nums)backtrack(make([]bool, len(nums)), []int{})return
}

c++

class Solution {
private:void backtrack(vector<int>& nums, vector<vector<int>>& ans, vector<bool>& vis, vector<int>& row) {if (row.size() == nums.size()) {ans.emplace_back(row);return;}for (int i = 0; i < nums.size(); ++i) {if (vis[i] || (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1])) {continue;}row.emplace_back(nums[i]);vis[i] = true;backtrack(nums, ans, vis, row);row.pop_back();vis[i] = false;}}
public:vector<vector<int>> permuteUnique(vector<int>& nums) {vector<vector<int>> ans;vector<int> row;vector<bool> vis(nums.size(), false);sort(nums.begin(), nums.end());backtrack(nums, ans, vis, row);return ans;}
};

c

int cmp(void* a, void* b) {return *(int*)a - *(int*)b;
}void backtrack(int* nums, int numSize, int** ans, int* ansSize, bool* vis, int* row, int idx) {if (idx == numSize) {int *tmp = malloc(sizeof(int) * numSize);memcpy(tmp, row, sizeof(int) * numSize);ans[(*ansSize)++] = tmp;return;}for (int i = 0; i < numSize; ++i) {if (vis[i] || (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1])) {continue;}row[idx] = nums[i];vis[i] = true;backtrack(nums, numSize, ans, ansSize, vis, row, idx + 1);vis[i] = false;}
}/*** Return an array of arrays of size *returnSize.* The sizes of the arrays are returned as *returnColumnSizes array.* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().*/
int** permuteUnique(int* nums, int numsSize, int* returnSize, int** returnColumnSizes){int** ans = malloc(sizeof(int*) * 2001);int* row = malloc(sizeof(int) * numsSize);bool* vis = malloc(sizeof(bool) * numsSize);memset(vis, false, sizeof(bool) * numsSize);qsort(nums, numsSize, sizeof(int), cmp);*returnSize = 0;backtrack(nums, numsSize, ans, returnSize, vis, row, 0);*returnColumnSizes = malloc(sizeof(int) * (*returnSize));for (int i = 0; i < *returnSize; i++) {(*returnColumnSizes)[i] = numsSize;}return ans;
}

python

class Solution:def permuteUnique(self, nums: List[int]) -> List[List[int]]:def backtrack(nums: List[int], ans: List[List[int]], vis: List[bool], row: List[int]):if len(row) == len(nums):ans.append(row.copy())returnfor i in range(len(nums)):if not vis[i]:if i > 0 and nums[i] == nums[i - 1] and not vis[i - 1]:continuerow.append(nums[i])vis[i] = Truebacktrack(nums, ans, vis, row)row.pop()vis[i] = Falsenums.sort()ans = []backtrack(nums, ans, [False] * len(nums), [])return ans

java

class Solution {public List<List<Integer>> permuteUnique(int[] nums) {List<List<Integer>> ans = new ArrayList<>();Arrays.sort(nums);backtrack(nums, ans, new boolean[nums.length], new LinkedList<>());return ans;}private void backtrack(int[] nums, List<List<Integer>> ans, boolean[] vis, Deque<Integer> row) {if (row.size() == nums.length) {ans.add(new ArrayList<>(row));return;}for (int i = 0; i < nums.length; ++i) {if (vis[i] || (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1])) {continue;}row.push(nums[i]);vis[i] = true;backtrack(nums, ans, vis, row);row.pop();vis[i] = false;}}
}

非常感谢你阅读本文~
欢迎【点赞】【收藏】【评论】~
放弃不难，但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子：https://le-yi.blog.csdn.net/ 博客原创~