力扣第四十七题——全排列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

完整代码

 int* vis;void backtrack(int* nums, int numSize, int** ans, int* ansSize, int idx, int* perm) {if (idx == numSize) {int* tmp = malloc(sizeof(int) * numSize);memcpy(tmp, perm, 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;}perm[idx] = nums[i];vis[i] = 1;backtrack(nums, numSize, ans, ansSize, idx + 1, perm);vis[i] = 0;}
}int cmp(void* a, void* b) {return *(int*)a - *(int*)b;
}int** permuteUnique(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {int** ans = malloc(sizeof(int*) * 2001);int* perm = malloc(sizeof(int) * 2001);vis = malloc(sizeof(int) * numsSize);memset(vis, 0, sizeof(int) * numsSize);qsort(nums, numsSize, sizeof(int), cmp);*returnSize = 0;backtrack(nums, numsSize, ans, returnSize, 0, perm);*returnColumnSizes = malloc(sizeof(int) * (*returnSize));for (int i = 0; i < *returnSize; i++) {(*returnColumnSizes)[i] = numsSize;}return ans;
}

思路详解

整体思路

1. 排序：首先对数组进行排序，以便在后续过程中可以轻松跳过重复的数字。
2. 回溯：使用回溯算法生成所有可能的全排列。
3. 去重：在生成全排列的过程中，通过一个布尔数组vis来标记某个数字是否已经被使用，以及通过比较相邻数字是否相等来跳过重复的排列。

详细步骤

1. 排序函数cmp

• cmp函数是一个比较函数，用于qsort函数进行排序。它比较两个整数的值，并返回它们之间的差值。

2. 主函数permuteUnique

• 初始化：分配内存给结果数组ans、排列数组perm和访问标记数组vis。
• 排序：调用qsort对输入数组nums进行排序。
• 调用回溯函数：调用backtrack函数开始生成全排列。
• 设置返回列大小：为每个排列分配列大小，即numsSize。

3. 回溯函数backtrack

• 终止条件：当idx等于numSize时，表示一个排列已经生成完毕，将其复制到结果数组ans中。
• 遍历数组：遍历输入数组nums，尝试将每个数字放入当前排列的idx位置。
• 剪枝：如果当前数字已经被访问过，或者当前数字与前一个数字相同且前一个数字未被访问过，则跳过当前循环，以避免生成重复的排列。
• 递归：将当前数字标记为已访问，并将其放入排列数组perm中，然后递归调用backtrack函数处理下一个位置。
• 撤销选择：在递归返回后，将当前数字标记为未访问，以便在后续的迭代中可以重新使用。

代码亮点

• 去重：通过排序和比较相邻数字，巧妙地避免了生成重复的排列。
• 回溯算法：使用回溯算法高效地生成所有可能的全排列。
• 内存管理：动态分配和释放内存，以存储生成的排列和访问标记。

知识点精炼

1. 排序：

   • 使用qsort函数对数组进行排序，以便于后续去重操作。

2. 回溯算法：

   • 利用回溯算法遍历所有可能的组合，并在满足条件时生成全排列。

3. 去重策略：

   • 通过排序和相邻元素比较，避免在回溯过程中生成重复的排列。

4. 布尔数组：

   • 使用布尔数组vis记录每个元素是否已被使用，确保每个元素在每个排列中只出现一次。

5. 动态内存分配：

   • 动态分配内存以存储全排列结果ans、排列数组perm和访问标记数组vis。

6. 剪枝优化：

   • 在回溯过程中，通过剪枝操作跳过不可能生成有效排列的分支，提高算法效率。

7. 递归与迭代：

   • 结合递归和迭代，实现深度优先搜索（DFS）来生成全排列。

8. 内存释放：

   • 在递归返回时，恢复现场，释放不必要的资源，避免内存泄漏。

9. 比较函数：

   • 实现cmp比较函数，作为qsort的参数，用于数组元素的排序。

10. 返回值与参数：

    • 通过指针参数返回全排列结果及其大小，以及每个排列的列大小。

 优化方案

去重优化

• 排序后去重：在回溯之前先对数组进行排序，这样可以在生成排列时更容易地跳过重复的元素。
• 位运算去重：对于小范围的整数，可以使用位运算来标记已访问的元素，减少内存使用和提高访问速度。

2. 回溯剪枝

• 提前终止：在递归过程中，如果发现某个分支不可能生成有效排列，应立即终止该分支的递归。
• 按字典序排列：在回溯时，保持元素按字典序排列，可以更早地发现重复并剪枝。

3. 数据结构优化

• 原地交换：使用原地交换而非额外的数组来存储排列，可以减少内存使用和复制操作。
• 栈代替递归：将递归改为使用栈，可以减少函数调用的开销。

4. 算法优化

• 迭代而非递归：在某些情况下，迭代可能比递归更高效，因为它避免了函数调用的开销。
• 分支限界：使用分支限界技术，只生成那些有希望成为有效排列的分支。

5. 并行计算

• 多线程：对于大型问题，可以使用多线程并行生成排列的不同分支。
• 分布式计算：将问题分割成多个子问题，在分布式系统中并行解决。

6. 编译器优化

• 编译器优化选项：使用编译器的优化选项，如-O2或-O3，可以自动进行某些优化。