Answer to Question #301349 in C++ for Navjot

Question

Given an equation x1 + x2 + · · · + xn = k, where k is a

constant, and x1, x2, . . . ,xn are nonnegative integers (which are considered

as variables in the equation), list all the solutions. Write a C

or C++ program to solve this problem. The input is a pair of integers

(n, k) with k 

Answer 1

#include <iostream>
using namespace std;


void print_array(int x[], int n) {
    for (int i=0; i<n; i++) {
        cout << x[i] << " ";
    }
    cout << endl;
}


void find_solutions(int x[], int m, int n, int k) {
    // Sum of x[m], ..., x[n-1] should be equal k
    if ( m == n) {
        return;
    }


    if ( k == 0) {
        print_array(x, n);
        return;
    }
    
    for (int i=0; i<k; i++) {
        x[m] = i;
        find_solutions(x, m+1, n, k-i);
    }
    x[m] = k;
    print_array(x, n);
    x[m] = 0;
}


int main() {
    int x[10] = {0};
    int n;
    cin >> n;
    if (n > 10) {
        cout << "n is toot big" << endl;
        exit(1);
    }

    int k;
    cin >> k;
    
    cout << endl;
    find_solutions(x, 0, n, k);

    return 0;
}