Using backtracking to get all ways to write a number as the result to the multiplication of its divisors via /r/learnprogramming


Using backtracking to get all ways to write a number as the result to the multiplication of its divisors

sorry for the title, im bad at english.what i mean is, by example if you enter 30, you should get

2 3 5 2 15 3 10 5 6 

my code is

#include <iostream> #include <fstream> using namespace std; int divizori[100]; int s; int nr_div; int rez[100]; void generate() { for (int i = 2; i <= s / 2; i++) if (s%i == 0) { divizori[nr_div] = i; nr_div++; } } bool valid(int k) { for (int i = 0; i < k; i++) { if (rez[i] == rez[k] || rez[i]>rez[k]) return false; } if (k > nr_div) return false; return true; } bool solution(int k) { int produs = 1; for (int i = 0; i < k; i++) produs *= rez[i]; if (produs == s) return true; else return false; } void display(int k) { cout << endl; for (int i = 0; i < k; i++) cout << rez[i] << " "; } void backtrack(int k) { for (int i = k; i < nr_div; i++) { rez[k] = divizori[i]; if (valid(k)) { if (solution(k)) { display(k); } else backtrack(k + 1); } } } int main() { cin >> s; generate(); backtrack(0); return 0; } 

with this, not only do i get the same sequence multiple times (i dont understand how), but i also dont get all the combinations.what am i doing wrong?

Submitted July 10, 2017 at 02:56PM by YoYeasa
via reddit http://ift.tt/2tHhUMA

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s