Problem: Write a program to print all unique combinations of factors of a given number using the backtracking algorithm in C++, Java, and Python.

Example:

We can easily solve this problem using the backtracking approach.

The idea is to multiply the iterating number to the product and check whether the product is less, is equal, or exceeds the number.

If the product is less, we multiply the next number to the product and check again.

If the product is equal to the number, we will output the combination of the factors multiplied to form the product, then remove (divide) the last multiplied number from the product (i.e. backtrack) and test out by multiplying the next number to the product.

If the product exceeds the number, we repeat the same backtrack process.

To know which combinations of factors have formed the product, we will store each multiplied number into the list or stack. The time we remove any number from the product we also pop it out from the list.

Here is the implementation of the above method in Python, C++, and Java.

Python

C++

Java

Output:

Factors combination output

In findCombinations(n, product) function declaration n is the next number to be multiplied to the product variable.

With each recursive call product value is updated and compared with the num value.

If product==num, we print the combination of factors in the list and return to last recursive call to remove the last multiplied factor from the product and test out with the next iterative x value (i.e. backtrack).

we repeat the recursive call for the same value of x i.e. findCombinations(x, product) because the combination could include duplicate factors, example: 16 = [2, 2, 2, 2].

In Python and C++ program, we are using list as stack.

In this tutorial, we learned to print all combination of factors of a given number using backtracking method in C++, Java and Python programming languages.

Leave a Reply