Prerequisite :- recursion
Problem :- Given three integers S, P, and k. Find if there exist k integers (n1, n2, …, nk) such that their sum is S and their product is P. If such integers exist, print them out. Otherwise, print “NO”.
Explanation :-
Find all the factors of P.
Factors of P will include 1, P itself, and any other number between 2 and P-1 that divides P evenly.
Use a recursive function that takes the current sum (s), product (p), the remaining count of integers to find (k), a vector to store the solution (soln), and the list of factors (factors).
In each recursive call, iterate through the factors and try to use each factor as a candidate integer.
For each factor considered, check if it evenly divides the current product (p). If it does, add it to the solution and recursively call the function with updated parameters.
Continue exploring until, find a sequence that satisfies both the sum and product conditions or until exhaust all possible combinations.
If a valid sequence is found, the function returns true; otherwise, it returns false.
C++ Solution:-
#include <bits/stdc++.h>
using namespace std;
bool func(int s, int p, int k, vector < int > & soln, vector < int > & factors) {
if (k == 0) return (s == 0 && p == 1);
for (int a: factors) {
if ((p % a) != 0) continue;
soln.push_back(a);
if (func(s - a, p / a, k - 1, soln, factors)) return true;
soln.pop_back();
}
return false;
}
int main() {
int s, p, k;
cin >> s >> p >> k;
vector < int > factors;
factors.push_back(1);
factors.push_back(p);
for (int i = 2; i < p; i++)
if (p % i == 0) factors.push_back(i);
vector < int > soln;
if (!func(s, p, k, soln, factors)) cout << "NO" << endl;
else
for (auto a: soln) cout << a << " ";
}