What your code is doing is finding the 3-combinations of [1, ..., n] that have a given sum. So your questions boils down to "How do you find the k-combinations of n items recursively?"
Combinations do exhibit recursive structure. Combinations can be generated recursively by building them incrementally in sorted order. To generate all k-combinations of a set of n items, you start with a partial combination P, which is a subset of items already selected. If the length of P is m, where m is less than k, the next step is to complete P by appending all possible combinations of length k minus m formed from the items that come after the last element of P. This ensures that combinations are constructed in sorted order and without repetition.
Code below:
#include <iostream>
#include <vector>
using vectors = std::vector<std::vector<int>>;
// helper function to give the recursive call
// the signature we want ...
void combinations_aux(
int n, int k, int start, std::vector<int>& current, vectors& result) {
// Base case: if the combination has the required size, add it to the result
if (current.size() == k) {
result.push_back(current);
return;
}
// Recursive case: try all possible next elements
for (int i = start; i <= n; ++i) {
current.push_back(i);
combinations_aux(n, k, i + 1, current, result);
current.pop_back();
}
}
vectors combinations(int n, int k) {
std::vector<std::vector<int>> result;
std::vector<int> current;
combinations_aux(n, k, 1, current, result);
return result;
}
vectors triples_of_given_sum(int n, int sum) {
vectors output;
for (auto combo : combinations(n, 3)) {
if (combo[0] + combo[1] + combo[2] == sum) {
output.push_back(combo);
}
}
return output;
}
int main() {
for (const auto& tri : triples_of_given_sum(20, 15)) {
std::cout << tri[0] << " " << tri[1] << " " << tri[2] << "\n";
}
return 0;
}