Question

How to find all possible ways to write a positive integer as a sum of positive integers in C++

Answer 1

#include <iostream>
#include <vector>

// Print a partition stored in 'vec' in the form "a + b + c"
void print_vector(const std::vector<int>& vec) {
    for (int i = 0; i < vec.size(); i++) {
        if (i > 0) std::cout << " + ";   // add plus signs between numbers
        std::cout << vec[i];
    }
    std::cout << "\n";
}

/*
    Generate all partitions of a number using non-decreasing sequences.

    vec       – current partial partition being built
    start     – the smallest number allowed next (prevents duplicates like 2+1 vs 1+2)
    remaining – how much is left to reach the target sum

    When remaining == 0, vec contains a complete valid partition.
*/
void partitions(std::vector<int>& vec, int start, int remaining) {
    // Base case: exact sum reached
    if (remaining == 0) {
        if (vec.size() >= 2)      // enforce "two or more integers"
            print_vector(vec);
        return;
    }

    // Try all next values from 'start' up to 'remaining'
    for (int j = start; j <= remaining; j++) {
        vec.push_back(j);                     // choose j
        partitions(vec, j, remaining - j);    // recurse with reduced remainder
        vec.pop_back();                       // undo choice (backtrack)
    }
}

int main() {
    int n = 5;                 // number to partition
    std::vector<int> vec;      // holds current partition
    
    partitions(vec, 1, n);     // start with smallest allowed value = 1
}



/*
run:

1 + 1 + 1 + 1 + 1
1 + 1 + 1 + 2
1 + 1 + 3
1 + 2 + 2
1 + 4
2 + 3

*/

 

70+ SQL courses for beginners and professionals

Answer 2

#include <iostream>
#include <vector>

/*
    Generate all ways to write a positive integer n
    as a sum of positive integers (integer partitions).

    Example for n = 5:
    [
      [ 5 ],
      [ 4, 1 ],
      [ 3, 2 ],
      [ 3, 1, 1 ],
      [ 2, 2, 1 ],
      [ 2, 1, 1, 1 ],
      [ 1, 1, 1, 1, 1 ]
    ]
*/

// Backtracking helper function
void backtrack(int remaining, int maxValue,
               std::vector<int>& current,
               std::vector<std::vector<int>>& results)
{
    // If nothing remains, we found a valid partition
    if (remaining == 0) {
        results.push_back(current);
        return;
    }

    // Try next numbers from maxValue down to 1
    for (int next = std::min(remaining, maxValue); next >= 1; next--) {
        current.push_back(next); // choose
        backtrack(remaining - next, next, current, results); // explore
        current.pop_back(); // un-choose (backtrack)
    }
}

// Function that returns all partitions of n
std::vector<std::vector<int>> partitions(int n) {
    std::vector<std::vector<int>> results;
    std::vector<int> current;
    backtrack(n, n, current, results);
    
    return results;
}

int main() {
    std::vector<std::vector<int>> result = partitions(5);

    std::cout << "[" << std::endl;
    for (size_t i = 0; i < result.size(); i++) {
        std::cout << "  [ ";
        for (size_t j = 0; j < result[i].size(); j++) {
            std::cout << result[i][j];
            if (j < result[i].size() - 1)
                std::cout << ", ";
        }
        std::cout << " ]";
        if (i < result.size() - 1)
            std::cout << "," << std::endl;
        else
            std::cout << std::endl;
    }
    std::cout << "]" << std::endl;
}



/*
run:

[
  [ 5 ],
  [ 4, 1 ],
  [ 3, 2 ],
  [ 3, 1, 1 ],
  [ 2, 2, 1 ],
  [ 2, 1, 1, 1 ],
  [ 1, 1, 1, 1, 1 ]
]

*/

 

70+ SQL courses for beginners and professionals