如何用递归函数生成C++偶数长度整数数组的所有配对组合？

我有一个长度为偶数的int类型数组arr[]，需要将数组中的每个元素与另一个元素配对，存入unordered_map<int, int>类型的pairs中。当数组长度大于2时，存在多种配对可能性，需求是生成所有可能的配对集合。

示例说明 #

比如数组：

int arr[4] = {1, 2, 3, 4};

对应的配对集合有三种：

pairs = {{1, 2}, {2, 1}, {3, 4}, {4, 3}};//1和2配对，3和4配对
pairs = {{1, 3}, {3, 1}, {2, 4}, {4, 2}};//1和3配对，2和4配对
pairs = {{1, 4}, {4, 1}, {2, 3}, {3, 2}};//1和4配对，2和3配对

当前代码与问题 #

我尝试用递归方法，通过标记已配对元素遍历所有可能配对，但没能成功实现。以下是我的代码，需要补全pairUp函数的递归逻辑，运行pairUp()后要得到指定输出：

#include <iostream>
#include <deque>
#include <unordered_map>
int n = 4;
std::unordered_map <int, int> pairs;
std::deque <int> arr = {0, 1, 2, 3};
std::deque <bool> paired = {false, false, false, false};
bool finishedPairing() {
    for (int i = 0; i < n; i++) {
        if (paired[i] == false) { return false; }
    }
    return true;
}
void pairUp() {
    if (finishedPairing()) {
        std::cout << "\nNew Set:\n";
        for (int i = 0; i < 4; i++) {
            std::cout << i << " is paired with " << pairs[i] << '\n';
        }
        return;
    }
//需要补充的C++代码
}
int main () {
    pairUp();
    return 0;
}

期望输出 #

New Set:
0 is paired with 1
1 is paired with 0
2 is paired with 3
3 is paired with 2

New Set:
0 is paired with 2
1 is paired with 3
2 is paired with 0
3 is paired with 1

New Set:
0 is paired with 3
1 is paired with 2
2 is paired with 1
3 is paired with 0

补全后的代码与逻辑 #

递归核心思路：每次找到第一个未配对元素，遍历所有其他未配对元素完成配对，标记状态后进入下一层递归；递归返回后回溯取消标记，尝试下一种配对可能。

补全后的pairUp函数代码：

void pairUp() {
    if (finishedPairing()) {
        std::cout << "\nNew Set:\n";
        for (int i = 0; i < 4; i++) {
            std::cout << i << " is paired with " << pairs[i] << '\n';
        }
        return;
    }

    // 定位第一个未配对的元素
    int first = -1;
    for (int i = 0; i < n; i++) {
        if (!paired[i]) {
            first = i;
            break;
        }
    }

    // 遍历所有可配对的未配对元素
    for (int i = first + 1; i < n; i++) {
        if (!paired[i]) {
            // 记录双向配对关系
            pairs[first] = arr[i];
            pairs[arr[i]] = first;
            // 标记为已配对
            paired[first] = true;
            paired[i] = true;

            // 递归处理剩余元素
            pairUp();

            // 回溯：恢复状态，尝试下一种配对
            paired[first] = false;
            paired[i] = false;
            pairs.erase(first);
            pairs.erase(arr[i]);
        }
    }
}

逻辑细节说明

1. 固定第一个未配对元素：避免生成重复的配对集合（比如先配对0&1再配对2&3，和先配对2&3再配对0&1属于同一种集合，固定第一个未配对元素的配对对象可减少冗余计算）。
2. 双向配对记录：确保pairs中同时存储a→b和b→a的映射关系，符合需求。
3. 回溯机制：递归返回后恢复配对标记和映射记录，保证后续循环能正确尝试下一种配对组合。

若数组arr的元素不是连续索引（比如示例中的{1,2,3,4}），只需调整配对记录的逻辑为pairs[arr[first]] = arr[i]; pairs[arr[i]] = arr[first];，paired数组按索引标记的逻辑无需修改。

内容的提问来源于stack exchange，提问作者Hudson