🌺The Begin🌺点点关注，收藏不迷路🌺

1. 问题描述

给定一个可能包含重复数字的序列 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] ]

2. 解题思路

2.1 回溯算法

1. 排序数组：便于跳过重复元素
2. 递归回溯：
   • 选择当前数字
   • 递归处理剩余数字
   • 回溯撤销选择
3. 去重关键：
   • 同一层级不重复选择相同数字
   • 使用访问标记数组避免重复使用

2.2 剪枝优化

• 跳过已使用的元素
• 跳过同一层级的重复元素

3. 代码实现

#include <stdlib.h>
#include <string.h>

int cmp(const void* a, const void* b) {
    return *(int*)a - *(int*)b;
}

void backtrack(int* nums, int numsSize, int* used, int* path, int depth, 
              int** result, int* resultSize, int** returnColumnSizes) {
    // 找到一个完整排列
    if (depth == numsSize) {
        result[*resultSize] = (int*)malloc(sizeof(int) * numsSize);
        memcpy(result[*resultSize], path, sizeof(int) * numsSize);
        (*returnColumnSizes)[*resultSize] = numsSize;
        (*resultSize)++;
        return;
    }

    for (int i = 0; i < numsSize; i++) {
        // 跳过已使用的元素
        if (used[i]) continue;
        
        // 去重：跳过同一层级的重复元素
        if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) continue;
        
        // 选择当前元素
        used[i] = 1;
        path[depth] = nums[i];
        
        // 递归处理下一层
        backtrack(nums, numsSize, used, path, depth + 1, 
                 result, resultSize, returnColumnSizes);
        
        // 回溯撤销选择
        used[i] = 0;
    }
}

int** permuteUnique(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
    // 排序数组以便去重
    qsort(nums, numsSize, sizeof(int), cmp);
    
    // 初始化结果存储
    *returnSize = 0;
    int maxSize = 1;
    for (int i = 2; i <= numsSize; i++) maxSize *= i;
    int** result = (int**)malloc(sizeof(int*) * maxSize);
    *returnColumnSizes = (int*)malloc(sizeof(int) * maxSize);
    
    // 初始化路径和访问标记
    int* path = (int*)malloc(sizeof(int) * numsSize);
    int* used = (int*)calloc(numsSize, sizeof(int));
    
    // 回溯求解
    backtrack(nums, numsSize, used, path, 0, result, returnSize, returnColumnSizes);
    
    free(path);
    free(used);
    return result;
}

4. 代码解析

4.1 排序函数

int cmp(const void* a, const void* b)

• 用于qsort的升序排序

4.2 回溯函数

void backtrack(...)

1. 终止条件：depth == numsSize时保存结果
2. 循环处理：遍历所有数字
3. 剪枝：
   • 跳过已使用的元素used[i]
   • 跳过重复元素nums[i] == nums[i-1] && !used[i-1]
4. 递归调用：处理下一层选择

4.3 主函数

int** permuteUnique(...)

1. 排序输入数组
2. 初始化结果存储
3. 调用回溯函数
4. 返回结果

5. 复杂度分析

• 时间复杂度：O(n*n!)，最坏情况下需要遍历所有排列
• 空间复杂度：O(n)，递归栈深度和临时数组

6. 测试用例

测试用例1：

int nums[] = {1,1,2};
// 预期输出：[[1,1,2],[1,2,1],[2,1,1]]

测试用例2：

int nums[] = {1,2,3};
// 预期输出：6种排列组合

7. 关键点总结

✅ 排序预处理：便于跳过重复元素
✅ 访问标记数组：避免重复使用同一元素
✅ 层级去重：确保结果唯一性
✅ 回溯框架：经典的回溯算法实现

8. 扩展思考

• 如何优化内存使用？
• 如何输出字典序的排列？
• 如何扩展到组合问题？

---

📌 总结：全排列II问题展示了回溯算法处理重复元素的技巧，通过排序和剪枝优化，可以高效解决这类排列问题。掌握这种方法对解决类似问题很有帮助！

🌺The End🌺点点关注，收藏不迷路🌺