有重复元素的排列问题代码详细解释

有重复元素的排列问题是指即使某些元素在数组中出现了多次，也需要考虑其所有可能的不同排列组合。解决这类问题时，通常需要避免重复计数和重复生成相同的排列。一种常见的方法是结合动态规划和哈希集合（如 C++ 中的 unordered_set）来跟踪已经生成的排列。

下面是一个简单的C++代码示例，用于生成有重复元素的数组的所有排列：

#include <iostream>
#include <vector>
#include <unordered_set>

std::vector<std::vector<int>> permuteWithDuplicates(std::vector<int>& nums) {
    std::vector<std::vector<int>> result;
    std::unordered_set<std::vector<int>> used;
    
    permute(nums, 0, result, used);
    return result;
}

void permute(std::vector<int>& nums, int start, std::vector<std::vector<int>>& result, std::unordered_set<std::vector<int>>& used) {
    if (start == nums.size()) {
        result.push_back(nums);
    } else {
        for (size_t i = start; i < nums.size(); ++i) {
            // 如果当前元素还没被用过，则尝试使用
            if (used.find(nums) == used.end()) {
                used.insert(nums);
                swap(nums[start], nums[i]);
                
                permute(nums, start + 1, result, used);  // 递归调用，处理下一个元素

                // 回溯，撤销当前操作，因为我们要考虑其他未使用的元素
                swap(nums[start], nums[i]);
                used.erase(nums);
            }
        }
    }
}

int main() {
    std::vector<int> nums = {1, 1, 2};
    std::vector<std::vector<int>> result = permuteWithDuplicates(nums);

    for (const auto& permutation : result) {
        std::cout << "[";
        for (int num : permutation) {
            std::cout << num << " ";
        }
        std::cout << "]" << std::endl;
    }

    return 0;
}

在这个代码里，`permuteWithDuplicates` 是主函数，负责初始化结果容器、哈希集合以及调用辅助函数 `permute`。`permute` 函数通过遍历数组，选择一个未使用过的元素，并将其放置在当前序列的起始位置，然后递归地处理其余部分。如果遇到已添加到哈希集合中的元素，表示这是一次重复，所以会跳过该元素，直到遍历完所有可能的位置。