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:
Input: 16
Output: [2, 2, 2, 2]
[2, 2, 4]
[2, 8]
[4, 4]
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
l = []
num = int(input("Enter a number: "))
def findCombinations(n, product):
global l
#Base condition
if product == num:
print(l)
return
for x in range(n, int(num/2)+1):
#If product exceeds num -> return to last recursive call
if product*x > num:
return
#Add number to product i.e. multiply
product = product * x
l.append(x)
#Recursive call with same number
findCombinations(x, product)
#Backtrack
l.pop()
product = product//x
findCombinations(2,1)
C++
// Online C++ compiler to run C++ program online
#include <list>
#include <iostream>
std::list<int> l;
int num = 0;
//Function to display list of factors
void print(std::list<int> l){
for (auto const& i: l) {
std::cout << i << " ";
}
std::cout << "\n";
}
void findCombinations(int n, int product){
//Base condition
if(product == num){
print(l);
return;
}
for(int x=n; x<(num/2)+1; x++){
//If product exceeds num -> return to last recursive call
if(product*x > num)
return;
//Add number to product i.e. multiply
product = product * x;
l.push_back(x);
//Recursive call with same number
findCombinations(x, product);
//Backtrack
l.pop_back();
product = product/x;
}
}
int main() {
std::cout << "Enter number: ";
std::cin >> num;
findCombinations(2,1);
return 0;
}Java
import java.util.Stack;
import java.util.Scanner;
class Main {
static Stack<Integer> l = new Stack<>();
static int num;
public static void main(String[] args) {
Scanner in=new Scanner(System.in);
System.out.print("Enter number: ");
num = in.nextInt();
findCombinations(2,1);
}
private static void findCombinations(int n, int product){
//Base condition
if(product == num){
System.out.println(l);
return;
}
for(int x=n; x<(num/2)+1; x++){
//If product exceeds num -> return to last recursive call
if(product*x > num)
return;
//Add number to product i.e. multiply
product = product * x;
l.push(x);
//Recursive call with same number
findCombinations(x, product);
//Backtrack
l.pop();
product = product/x;
}
}
}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.