C++ 生成数组的唯一排列算法 - 避免重复排列 - 常规

一个简单的方法是使用递归来生成所有可能的排列。首先，我们将原始数组进行排序，以确保重复元素相邻。然后，我们使用一个布尔数组来标记哪些元素已经被使用过。

以下是一个示例代码：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void permuteUnique(vector<int>& nums, vector<int>& permutation, vector<bool>& used, vector<vector<int>>& result) {
    // 如果当前排列长度等于原始数组长度，则将当前排列加入结果集
    if (permutation.size() == nums.size()) {
        result.push_back(permutation);
        return;
    }

    for (int i = 0; i < nums.size(); i++) {
        // 如果当前元素已经被使用过，则跳过
        if (used[i]) {
            continue;
        }

        // 如果当前元素与前一个元素相同，并且前一个元素已经被使用过，则跳过
        if (i > 0 && nums[i] == nums[i - 1] && used[i - 1]) {
            continue;
        }

        // 将当前元素加入排列，并标记为已使用
        permutation.push_back(nums[i]);
        used[i] = true;

        // 递归生成下一个元素的排列
        permuteUnique(nums, permutation, used, result);

        // 恢复状态，以便生成其他排列
        permutation.pop_back();
        used[i] = false;
    }
}

vector<vector<int>> permuteUnique(vector<int>& nums) {
    vector<vector<int>> result;
    vector<int> permutation;
    vector<bool> used(nums.size(), false);

    // 首先对原始数组进行排序
    sort(nums.begin(), nums.end());

    permuteUnique(nums, permutation, used, result);

    return result;
}

int main() {
    vector<int> nums = {1, 2, 2, 3, 3};
    vector<vector<int>> result = permuteUnique(nums);

    for (const auto& permutation : result) {
        for (const auto& num : permutation) {
            cout << num << ' ';
        }
        cout << endl;
    }

    return 0;
}

输出结果为：