整数划分问题c++递归

整数划分问题是求解将给定的一个正整数表示为一系列非负整数之和的所有可能性。在C++中，可以使用递归来解决这个问题。递归的基本思路是，对于每个数字n，我们有两个选项：

1. 包含当前数字n，然后对剩下的数(n-1)继续递归求解。
2. 不包含当前数字n，直接对剩下的数(n)进行递归。

以下是使用递归实现的简单示例代码：

#include <vector>
using namespace std;

vector<vector<int>> findPartitions(int n) {
    vector<vector<int>> result; // 存放结果的二维向量
    vector<int> current_partition; // 当前的分割方案

    partitionHelper(n, 0, current_partition, result);
    return result;
}

void partitionHelper(int n, int start, vector<int>& current_partition, vector<vector<int>>& result) {
    if (start >= n) { // 搜索结束条件，如果开始索引大于等于n，说明已经找到了一种分割方式
        result.push_back(current_partition); // 将当前分割方案添加到结果中
        return;
    }

    // 两个分支：包含当前数字，不包含当前数字
    for (int i = start; i <= n; ++i) {
        current_partition.push_back(i); // 包含i
        partitionHelper(n - i, i, current_partition, result); // 对剩余部分继续递归
        current_partition.pop_back(); // 移除最后添加的i，回溯尝试下一个数字
    }
}