79218419

Date: 2024-11-23 17:21:56
Score: 2
Natty:
Report link

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;
}
Reasons:
  • Blacklisted phrase (1): How do you
  • RegEx Blacklisted phrase (2.5): do you find the
  • Long answer (-1):
  • Has code block (-0.5):
  • Contains question mark (0.5):
  • Starts with a question (0.5): What you
  • High reputation (-1):
Posted by: jwezorek