本文共 2223 字，大约阅读时间需要 7 分钟。
分析
这道题目要求找出所有从一个包含重复数字的数字集合中选出唯一数字的组合。题目中的关键难点在于，集合中的数字可能有重复，而由于每个数字只能被选一次，因此我们需要一种方法来确保每次选择的数字都是唯一的。此外，因为有重复的数字，为了更好地跟踪哪些数字已经被选择，我们需要使用一个布尔数组来记录每个位置是否已经被选中。
为了实现这一点，我们使用一个递归函数进行深度优先搜索，维护两个辅助数据结构：一个记录路径的向量road，以及一个标记数组judge。judge数组用于记录每个位置是否已经被选中。以下是具体的思路和解决方法：
排序数字集合：首先，我们对输入的数字集合进行排序。这是因为，通过排序，重复元素的位置会被收集在一起，方便我们在递归过程中进行处理。
标记数组的使用：我们维护一个标记数组judge，其中judge[i]为true表示第i个数字已经被选中，false表示未被选中。在递归过程中，标记数组将被修改，以反映当前路径中已经选中的数字。
递归函数的逻辑：递归函数的结束条件是当前路径的长度等于数字集合的长度。每当达到这个条件时，当前路径被 saving添加到结果中。
循环结构和条件控制：在递归函数内部，我们使用for循环遍历数字集合中的每一个数字。为了避免选取重复的数字，我们设置了一个条件：如果当前位置i已经被标记为true（已被选中），或者（i > 0且nums[i]等于nums[i-1]且judge[i-1]为false），那么我们跳过这个数字。这样可以确保我们不会选择相同的数字多次。否则，我们将当前位置标记为true，并将该数字添加到路径中，然后进行递归调用。
路径的回溯：在递归调用返回后，我们需要撤销当前位置的标记和路径中的数字，以便尝试其他可能的路径。
代码
以下是该问题的解决代码：
#include#include using namespace std;class Solution {private: vector vec; vector judge;public: vector permuteUnique(const vector & nums) { sort(nums.begin(), nums.end()); vector road; judge.resize(nums.size(), false); permuteHelper(nums, road, judge); return vec; } void permuteHelper(const vector & nums, vector & road, vector & judge) { if (road.size() == nums.size()) { vec.push_back(road); return; } for (int i = 0; i < nums.size(); ++i) { int data = nums[i]; if (judge[i] || (i > 0 && nums[i] == nums[i - 1] && !judge[i - 1])) { continue; } judge[i] = true; road.push_back(data); permuteHelper(nums, road, judge); road.pop_back(); judge[i] = false; } }};int main() { // 一个测试用例 vector nums = {1, 2, 2, 3}; Solution s; s.permuteUnique(nums); for (auto& v : s.vec) { cout << "{"; for (int num : v) { cout << num << ","; } cout << "}" << endl; } return 0;}
这个代码实现了以下步骤：
排序：使用sort函数对输入的数字集合进行了排序。
初始化标记数组：创建了一个标记数组judge，初始化为都为false，长度和数字集合的大小相同。
递归调用：调用递归函数permuteHelper，其接受nums、road和judge作为参数。
终止条件：当road的大小等于nums的大小时，即当前路径包含所有数字，记录该路径到vec中，并返回。
循环遍历：遍历每个数字，如果当前数字已经被选中或前一个数字已经被选过，且与当前数字相同且未被选过，则跳过当前数字。否则，标记当前数字为已选，添加到路径中，进行递归调用，然后撤销标记。
测试用例：代码的主函数调用permuteUnique函数，并输出结果。
转载地址：http://vnqgz.baihongyu.com/