Posted on by Kalkicode
Code Backtracking

Print all combinations of N length sequences whose product is M

Here given code implementation process.

// C Program
// Print all combinations of N length sequences whose product is M
#include <stdio.h>

void subSequences(int result[], int count, int product, int n, int m)
{
	if (count == n && product == m)
	{
		for (int i = 0; i < count; ++i)
		{
			// Display element value
			printf(" %d", result[i]);
		}
		printf("\n");
	}
	else if (product > m || count >= n)
	{
		return;
	}
	else
	{
		for (int i = 1; i <= m; ++i)
		{
			// Collect elements 
			result[count] = i;
			// Find subsequence by using recursively
			subSequences(result, count + 1, product *i, n, m);
		}
	}
}
void findSequence(int n, int m)
{
	if (n <= 0)
	{
		return;
	}
  	printf(" Length  : %d",n);
  	printf("\n Product %d\n",m);
	// Auxiliary array which is collect result
	int result[n];
	subSequences(result, 0, 1, n, m);
}
int main()
{
	// Length of sequences
	int n = 3;
	// Product
	int m = 28;
	// Test
	findSequence(n, m);
	return 0;
}

Output

 Length  : 3
 Product 28
 1 1 28
 1 2 14
 1 4 7
 1 7 4
 1 14 2
 1 28 1
 2 1 14
 2 2 7
 2 7 2
 2 14 1
 4 1 7
 4 7 1
 7 1 4
 7 2 2
 7 4 1
 14 1 2
 14 2 1
 28 1 1
// Java program for
// Print all combinations of N length sequences whose product is M
public class Combination
{
	public void subSequences(int[] result, int count, 
      int product, int n, int m)
	{
		if (count == n && product == m)
		{
			for (int i = 0; i < count; ++i)
			{
				// Display element value
				System.out.print(" " + result[i]);
			}
			System.out.print("\n");
		}
		else if (product > m || count >= n)
		{
			return;
		}
		else
		{
			for (int i = 1; i <= m; ++i)
			{
				// Collect elements 
				result[count] = i;
				// Find subsequence by using recursively
				subSequences(result, count + 1, 
                             product * i, n, m);
			}
		}
	}
	public void findSequence(int n, int m)
	{
		if (n <= 0)
		{
			return;
		}
		System.out.print(" Length : " + n);
		System.out.println("\n Product " + m);
		// Auxiliary array which is collect result
		int[] result = new int[n];
		subSequences(result, 0, 1, n, m);
	}
	public static void main(String[] args)
	{
		Combination task = new Combination();
		// Length of sequences
		int n = 3;
		// Product
		int m = 28;
		// Test
		task.findSequence(n, m);
	}
}

Output

 Length : 3
 Product 28
 1 1 28
 1 2 14
 1 4 7
 1 7 4
 1 14 2
 1 28 1
 2 1 14
 2 2 7
 2 7 2
 2 14 1
 4 1 7
 4 7 1
 7 1 4
 7 2 2
 7 4 1
 14 1 2
 14 2 1
 28 1 1
// Include header file
#include <iostream>

using namespace std;
// C++ program for
// Print all combinations of N length sequences whose product is M
class Combination
{
	public: void subSequences(int result[], int count, 
      						  int product, int n, int m)
	{
		if (count == n && product == m)
		{
			for (int i = 0; i < count; ++i)
			{
				// Display element value
				cout << " " << result[i];
			}
			cout << "\n";
		}
		else if (product > m || count >= n)
		{
			return;
		}
		else
		{
			for (int i = 1; i <= m; ++i)
			{
				// Collect elements 
				result[count] = i;
				// Find subsequence by using recursively
				this->subSequences(result, count + 1, 
                                   product *i, n, m);
			}
		}
	}
	void findSequence(int n, int m)
	{
		if (n <= 0)
		{
			return;
		}
		cout << " Length : " << n;
		cout << "\n Product " << m << endl;
		// Auxiliary array which is collect result
		int result[n];
		this->subSequences(result, 0, 1, n, m);
	}
};
int main()
{
	Combination *task = new Combination();
	// Length of sequences
	int n = 3;
	// Product
	int m = 28;
	// Test
	task->findSequence(n, m);
	return 0;
}

Output

 Length : 3
 Product 28
 1 1 28
 1 2 14
 1 4 7
 1 7 4
 1 14 2
 1 28 1
 2 1 14
 2 2 7
 2 7 2
 2 14 1
 4 1 7
 4 7 1
 7 1 4
 7 2 2
 7 4 1
 14 1 2
 14 2 1
 28 1 1
// Include namespace system
using System;
// Csharp program for
// Print all combinations of N length sequences whose product is M
public class Combination
{
	public void subSequences(int[] result, 
  		int count, 
  		int product, 
        int n, 
        int m)
	{
		if (count == n && product == m)
		{
			for (int i = 0; i < count; ++i)
			{
				// Display element value
				Console.Write(" " + result[i]);
			}
			Console.Write("\n");
		}
		else if (product > m || count >= n)
		{
			return;
		}
		else
		{
			for (int i = 1; i <= m; ++i)
			{
				// Collect elements 
				result[count] = i;
				// Find subsequence by using recursively
				this.subSequences(result, count + 1, 
                                  product * i, n, m);
			}
		}
	}
	public void findSequence(int n, int m)
	{
		if (n <= 0)
		{
			return;
		}
		Console.Write(" Length : " + n);
		Console.WriteLine("\n Product " + m);
		// Auxiliary array which is collect result
		int[] result = new int[n];
		this.subSequences(result, 0, 1, n, m);
	}
	public static void Main(String[] args)
	{
		Combination task = new Combination();
		// Length of sequences
		int n = 3;
		// Product
		int m = 28;
		// Test
		task.findSequence(n, m);
	}
}

Output

 Length : 3
 Product 28
 1 1 28
 1 2 14
 1 4 7
 1 7 4
 1 14 2
 1 28 1
 2 1 14
 2 2 7
 2 7 2
 2 14 1
 4 1 7
 4 7 1
 7 1 4
 7 2 2
 7 4 1
 14 1 2
 14 2 1
 28 1 1
package main
import "fmt"
// Go program for
// Print all combinations of N length sequences whose product is M
type Combination struct {}
func getCombination() * Combination {
	var me *Combination = &Combination {}
	return me
}
func(this Combination) subSequences(result[] int, 
	count int, 
	product int, 
	n int, 
	m int) {
	if count == n && product == m {
		for i := 0 ; i < count ; i++ {
			// Display element value
			fmt.Print(" ", result[i])
		}
		fmt.Print("\n")
	} else if product > m || count >= n {
		return
	} else {
		for i := 1 ; i <= m ; i++ {
			// Collect elements 
			result[count] = i
			// Find subsequence by using recursively
			this.subSequences(result, 
				count + 1, 
				product * i,
				n,
				m)
		}
	}
}
func(this Combination) findSequence(n, m int) {
	if n <= 0 {
		return
	}
	fmt.Print(" Length : ", n)
	fmt.Println("\n Product ", m)
	// Auxiliary array which is collect result
	var result = make([] int, n)
	this.subSequences(result, 0, 1, n, m)
}
func main() {
	var task * Combination = getCombination()
	// Length of sequences
	var n int = 3
	// Product
	var m int = 28
	// Test
	task.findSequence(n, m)
}

Output

 Length : 3
 Product 28
 1 1 28
 1 2 14
 1 4 7
 1 7 4
 1 14 2
 1 28 1
 2 1 14
 2 2 7
 2 7 2
 2 14 1
 4 1 7
 4 7 1
 7 1 4
 7 2 2
 7 4 1
 14 1 2
 14 2 1
 28 1 1
<?php
// Php program for
// Print all combinations of N length sequences whose product is M
class Combination
{
	public	function subSequences($result, 
                                   $count, 
                                   $product, 
                                   $n, 
                                   $m)
	{
		if ($count == $n && $product == $m)
		{
			for ($i = 0; $i < $count; ++$i)
			{
				// Display element value
				echo(" ".$result[$i]);
			}
			echo("\n");
		}
		else if ($product > $m || $count >= $n)
		{
			return;
		}
		else
		{
			for ($i = 1; $i <= $m; ++$i)
			{
				// Collect elements 
				$result[$count] = $i;
				// Find subsequence by using recursively
				$this->subSequences($result, 
                                    $count + 1, 
                                    $product * $i, 
                                    $n, 
                                    $m);
			}
		}
	}
	public	function findSequence($n, $m)
	{
		if ($n <= 0)
		{
			return;
		}
		echo(" Length : ".$n);
		echo("\n Product ".$m."\n");
		// Auxiliary array which is collect result
		$result = array_fill(0, $n, 0);
		$this->subSequences($result, 0, 1, $n, $m);
	}
}

function main()
{
	$task = new Combination();
	// Length of sequences
	$n = 3;
	// Product
	$m = 28;
	// Test
	$task->findSequence($n, $m);
}
main();

Output

 Length : 3
 Product 28
 1 1 28
 1 2 14
 1 4 7
 1 7 4
 1 14 2
 1 28 1
 2 1 14
 2 2 7
 2 7 2
 2 14 1
 4 1 7
 4 7 1
 7 1 4
 7 2 2
 7 4 1
 14 1 2
 14 2 1
 28 1 1
// Node JS program for
// Print all combinations of N length sequences whose product is M
class Combination
{
	subSequences(result, count, product, n, m)
	{
		if (count == n && product == m)
		{
			for (var i = 0; i < count; ++i)
			{
				// Display element value
				process.stdout.write(" " + result[i]);
			}
			process.stdout.write("\n");
		}
		else if (product > m || count >= n)
		{
			return;
		}
		else
		{
			for (var i = 1; i <= m; ++i)
			{
				// Collect elements 
				result[count] = i;
				// Find subsequence by using recursively
				this.subSequences(result, 
                                  count + 1, 
                                  product * i,
                                  n, 
                                  m);
			}
		}
	}
	findSequence(n, m)
	{
		if (n <= 0)
		{
			return;
		}
		process.stdout.write(" Length : " + n);
		console.log("\n Product " + m);
		// Auxiliary array which is collect result
		var result = Array(n).fill(0);
		this.subSequences(result, 0, 1, n, m);
	}
}

function main()
{
	var task = new Combination();
	// Length of sequences
	var n = 3;
	// Product
	var m = 28;
	// Test
	task.findSequence(n, m);
}
main();

Output

 Length : 3
 Product 28
 1 1 28
 1 2 14
 1 4 7
 1 7 4
 1 14 2
 1 28 1
 2 1 14
 2 2 7
 2 7 2
 2 14 1
 4 1 7
 4 7 1
 7 1 4
 7 2 2
 7 4 1
 14 1 2
 14 2 1
 28 1 1
#  Python 3 program for
#  Print all combinations of N length sequences whose product is M
class Combination :
	def subSequences(self, result, count, product, n, m) :
		if (count == n and product == m) :
			i = 0
			while (i < count) :
				#  Display element value
				print(" ", result[i], end = "")
				i += 1
			
			print(end = "\n")
		elif (product > m or count >= n) :
			return
		else :
			i = 1
			while (i <= m) :
				#  Collect elements 
				result[count] = i
				#  Find subsequence by using recursively
				self.subSequences(result, count + 1, 
                                  product * i, n, m)
				i += 1
			
		
	
	def findSequence(self, n, m) :
		if (n <= 0) :
			return
		
		print(" Length : ", n, end = "")
		print("\n Product ", m)
		#  Auxiliary list which is collect result
		result = [0] * (n)
		self.subSequences(result, 0, 1, n, m)
	

def main() :
	task = Combination()
	#  Length of sequences
	n = 3
	#  Product
	m = 28
	#  Test
	task.findSequence(n, m)

if __name__ == "__main__": main()

Output

 Length :  3
 Product  28
  1  1  28
  1  2  14
  1  4  7
  1  7  4
  1  14  2
  1  28  1
  2  1  14
  2  2  7
  2  7  2
  2  14  1
  4  1  7
  4  7  1
  7  1  4
  7  2  2
  7  4  1
  14  1  2
  14  2  1
  28  1  1
#  Ruby program for
#  Print all combinations of N length sequences whose product is M
class Combination 
	def subSequences(result, count, product, n, m) 
		if (count == n && product == m) 
			i = 0
			while (i < count) 
				#  Display element value
				print(" ", result[i])
				i += 1
			end

			print("\n")
		elsif (product > m || count >= n) 
			return
		else
 
			i = 1
			while (i <= m) 
				#  Collect elements 
				result[count] = i
				#  Find subsequence by using recursively
				self.subSequences(result, count + 1, product * i, n, m)
				i += 1
			end

		end

	end

	def findSequence(n, m) 
		if (n <= 0) 
			return
		end

		print(" Length : ", n)
		print("\n Product ", m, "\n")
		#  Auxiliary array which is collect result
		result = Array.new(n) {0}
		self.subSequences(result, 0, 1, n, m)
	end

end

def main() 
	task = Combination.new()
	#  Length of sequences
	n = 3
	#  Product
	m = 28
	#  Test
	task.findSequence(n, m)
end

main()

Output

 Length : 3
 Product 28
 1 1 28
 1 2 14
 1 4 7
 1 7 4
 1 14 2
 1 28 1
 2 1 14
 2 2 7
 2 7 2
 2 14 1
 4 1 7
 4 7 1
 7 1 4
 7 2 2
 7 4 1
 14 1 2
 14 2 1
 28 1 1
// Scala program for
// Print all combinations of N length sequences whose product is M
class Combination()
{
	def subSequences(result: Array[Int], 
      count: Int, product: Int, n: Int, m: Int): Unit = {
		if (count == n && product == m)
		{
			var i: Int = 0;
			while (i < count)
			{
				// Display element value
				print(" " + result(i));
				i += 1;
			}
			print("\n");
		}
		else if (product > m || count >= n)
		{
			return;
		}
		else
		{
			var i: Int = 1;
			while (i <= m)
			{
				// Collect elements 
				result(count) = i;
				// Find subsequence by using recursively
				subSequences(result, count + 1, 
                             product * i, n, m);
				i += 1;
			}
		}
	}
	def findSequence(n: Int, m: Int): Unit = {
		if (n <= 0)
		{
			return;
		}
		print(" Length : " + n);
		println("\n Product " + m);
		// Auxiliary array which is collect result
		var result: Array[Int] = Array.fill[Int](n)(0);
		subSequences(result, 0, 1, n, m);
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: Combination = new Combination();
		// Length of sequences
		var n: Int = 3;
		// Product
		var m: Int = 28;
		// Test
		task.findSequence(n, m);
	}
}

Output

 Length : 3
 Product 28
 1 1 28
 1 2 14
 1 4 7
 1 7 4
 1 14 2
 1 28 1
 2 1 14
 2 2 7
 2 7 2
 2 14 1
 4 1 7
 4 7 1
 7 1 4
 7 2 2
 7 4 1
 14 1 2
 14 2 1
 28 1 1
// Swift 4 program for
// Print all combinations of N length sequences whose product is M
class Combination
{
	func subSequences(_ result: inout[Int], 
  	_ count: Int, _ product: Int, 
    _ n: Int, _ m: Int)
	{
		if (count == n && product == m)
		{
			var i: Int = 0;
			while (i < count)
			{
				// Display element value
				print(" ", result[i], terminator: "");
				i += 1;
			}
			print(terminator: "\n");
		}
		else if (product > m || count >= n)
		{
			return;
		}
		else
		{
			var i: Int = 1;
			while (i <= m)
			{
				// Collect elements 
				result[count] = i;
				// Find subsequence by using recursively
				self.subSequences(&result, 
                                  count + 1, 
                                  product * i, 
                                  n, 
                                  m);
				i += 1;
			}
		}
	}
	func findSequence(_ n: Int, _ m: Int)
	{
		if (n <= 0)
		{
			return;
		}
		print(" Length : ", n, terminator: "");
		print("\n Product ", m);
		// Auxiliary array which is collect result
		var result: [Int] = Array(repeating: 0, count: n);
		self.subSequences(&result, 0, 1, n, m);
	}
}
func main()
{
	let task: Combination = Combination();
	// Length of sequences
	let n: Int = 3;
	// Product
	let m: Int = 28;
	// Test
	task.findSequence(n, m);
}
main();

Output

 Length :  3
 Product  28
  1  1  28
  1  2  14
  1  4  7
  1  7  4
  1  14  2
  1  28  1
  2  1  14
  2  2  7
  2  7  2
  2  14  1
  4  1  7
  4  7  1
  7  1  4
  7  2  2
  7  4  1
  14  1  2
  14  2  1
  28  1  1
// Kotlin program for
// Print all combinations of N length sequences whose product is M
class Combination
{
	fun subSequences(result: Array < Int > , 
                      count: Int, product: Int, 
                      n: Int, m: Int): Unit
	{
		if (count == n && product == m)
		{
			var i: Int = 0;
			while (i < count)
			{
				// Display element value
				print(" " + result[i]);
				i += 1;
			}
			print("\n");
		}
		else if (product > m || count >= n)
		{
			return;
		}
		else
		{
			var i: Int = 1;
			while (i <= m)
			{
				// Collect elements 
				result[count] = i;
				// Find subsequence by using recursively
				this.subSequences(result, 
                                  count + 1, 
                                  product * i,
                                  n,
                                  m);
				i += 1;
			}
		}
	}
	fun findSequence(n: Int, m: Int): Unit
	{
		if (n <= 0)
		{
			return;
		}
		print(" Length : " + n);
		println("\n Product " + m);
		// Auxiliary array which is collect result
		var result: Array < Int > = Array(n)
		{
			0
		};
		this.subSequences(result, 0, 1, n, m);
	}
}
fun main(args: Array < String > ): Unit
{
	val task: Combination = Combination();
	// Length of sequences
	val n: Int = 3;
	// Product
	val m: Int = 28;
	// Test
	task.findSequence(n, m);
}

Output

 Length : 3
 Product 28
 1 1 28
 1 2 14
 1 4 7
 1 7 4
 1 14 2
 1 28 1
 2 1 14
 2 2 7
 2 7 2
 2 14 1
 4 1 7
 4 7 1
 7 1 4
 7 2 2
 7 4 1
 14 1 2
 14 2 1
 28 1 1

Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment