Posted on by Kalkicode
Code Backtracking

Find all subsequences whose product is less than k in array

Here given code implementation process.

// C Program
// Find all subsequences whose product is less than k in array
#include <stdio.h>

void subSequences(int arr[], 
  int result[], 
    int start, 
      int count, 
        int product, 
          int n, 
            int k)
{
	if (product <= k)
	{
		for (int i = 0; i < count; ++i)
		{
			printf(" %d", result[i]);
		}
		printf("\n");
	}
	if (count >= n)
	{
		return;
	}
	else
	{
		for (int i = start + 1; i <= n; ++i)
		{
			// Collect elements 
			result[count] = i;
			subSequences(arr, result, i, 
                         count + 1, product *i, n, k);
		}
	}
}
// Handles the request to find resultant subsequences
void findProductSequence(int arr[], int n, int k)
{
	// Auxiliary array which is collect result
	int result[n];
	subSequences(arr, result, 0, 0, 1, n, k);
}
int main()
{
	int arr[] = {
		1 , 2 , 3 , 4
	};
	int n = sizeof(arr) / sizeof(arr[0]);
	// Product
	int k = 6;
	// Test
	//  
	findProductSequence(arr, n, k);
	return 0;
}

Output

 1
 1 2
 1 2 3
 1 3
 1 4
 2
 2 3
 3
 4
// Java program for
// Find all subsequences whose product is less than k in array
public class Combination
{
	public void subSequences(int[] arr, 
    int[] result, 
    int start, 
    int count, 
    int product, 
    int n, 
    int k)
	{
		if (product <= k)
		{
			for (int i = 0; i < count; ++i)
			{
				System.out.print(" " + result[i]);
			}
			System.out.print("\n");
		}
		if (count >= n)
		{
			return;
		}
		else
		{
			for (int i = start + 1; i <= n; ++i)
			{
				// Collect elements 
				result[count] = i;
				subSequences(arr, result, i, 
                             count + 1, 
                             product * i, 
                             n, k);
			}
		}
	}
	// Handles the request to find resultant subsequences
	public void findProductSequence(int[] arr, int n, int k)
	{
		// Auxiliary array which is collect result
		int[] result = new int[n];
		subSequences(arr, result, 0, 0, 1, n, k);
	}
	public static void main(String[] args)
	{
		Combination task = new Combination();
		int[] arr = {
			1 , 2 , 3 , 4
		};
		int n = arr.length;
		// Product
		int k = 6;
		// Test 
		task.findProductSequence(arr, n, k);
	}
}

Output

 1
 1 2
 1 2 3
 1 3
 1 4
 2
 2 3
 3
 4
// Include header file
#include <iostream>

using namespace std;
// C++ program for
// Find all subsequences whose product is less than k in array
class Combination
{
	public: void subSequences(
      	int arr[], 
      int result[], 
        int start, 
          int count, 
            int product, 
              int n, 
                int k)
	{
		if (product <= k)
		{
			for (int i = 0; i < count; ++i)
			{
				cout << " " << result[i];
			}
			cout << "\n";
		}
		if (count >= n)
		{
			return;
		}
		else
		{
			for (int i = start + 1; i <= n; ++i)
			{
				// Collect elements 
				result[count] = i;
				this->subSequences(arr, result, 
                                   i, count + 1, 
                                   product *i, 
                                   n, k);
			}
		}
	}
	// Handles the request to find resultant subsequences
	void findProductSequence(int arr[], int n, int k)
	{
		// Auxiliary array which is collect result
		int result[n];
		this->subSequences(arr, result, 0, 0, 1, n, k);
	}
};
int main()
{
	Combination *task = new Combination();
	int arr[] = {
		1 , 2 , 3 , 4
	};
	int n = sizeof(arr) / sizeof(arr[0]);
	// Product
	int k = 6;
	// Test 
	task->findProductSequence(arr, n, k);
	return 0;
}

Output

 1
 1 2
 1 2 3
 1 3
 1 4
 2
 2 3
 3
 4
// Include namespace system
using System;
// Csharp program for
// Find all subsequences whose product is less than k in array
public class Combination
{
	public void subSequences(
    int[] arr, 
    int[] result, 
    int start, 
    int count, 
    int product, 
    int n, 
    int k)
	{
		if (product <= k)
		{
			for (int i = 0; i < count; ++i)
			{
				Console.Write(" " + result[i]);
			}
			Console.Write("\n");
		}
		if (count >= n)
		{
			return;
		}
		else
		{
			for (int i = start + 1; i <= n; ++i)
			{
				// Collect elements 
				result[count] = i;
				this.subSequences(arr, result, 
                                  i, count + 1, 
                                  product * i, 
                                  n, 
                                  k);
			}
		}
	}
	// Handles the request to find resultant subsequences
	public void findProductSequence(int[] arr, int n, int k)
	{
		// Auxiliary array which is collect result
		int[] result = new int[n];
		this.subSequences(arr, result, 0, 0, 1, n, k);
	}
	public static void Main(String[] args)
	{
		Combination task = new Combination();
		int[] arr = {
			1 , 2 , 3 , 4
		};
		int n = arr.Length;
		// Product
		int k = 6;
		// Test 
		task.findProductSequence(arr, n, k);
	}
}

Output

 1
 1 2
 1 2 3
 1 3
 1 4
 2
 2 3
 3
 4
package main
import "fmt"
// Go program for
// Find all subsequences whose product is less than k in array
type Combination struct {}
func getCombination() * Combination {
	var me *Combination = &Combination {}
	return me
}
func(this Combination) subSequences(arr[] int, 
	result[] int, 
	start int, 
	count int, 
	product int, 
	n int, 
	k int) {
	if product <= k {
		for i := 0 ; i < count ; i++ {
			fmt.Print(" ", result[i])
		}
		fmt.Print("\n")
	}
	if count >= n {
		return
	} else {
		for i := start + 1 ; i <= n ; i++ {
			// Collect elements 
			result[count] = i
			this.subSequences(arr, result, 
				i, count + 1, 
				product * i, n, k)
		}
	}
}
// Handles the request to find resultant subsequences
func(this Combination) findProductSequence(arr[] int, 
	n int, k int) {
	// Auxiliary array which is collect result
	var result = make([] int, n)
	this.subSequences(arr, result, 0, 0, 1, n, k)
}
func main() {
	var task * Combination = getCombination()
	var arr = [] int {
		1,
		2,
		3,
		4,
	}
	var n int = len(arr)
	// Product
	var k int = 6
	// Test 
	task.findProductSequence(arr, n, k)
}

Output

 1
 1 2
 1 2 3
 1 3
 1 4
 2
 2 3
 3
 4
<?php
// Php program for
// Find all subsequences whose product is less than k in array
class Combination
{
	public	function subSequences($arr, 
                                   $result, 
                                   $start, 
                                   $count, 
                                   $product, 
                                   $n, 
                                   $k)
	{
		if ($product <= $k)
		{
			for ($i = 0; $i < $count; ++$i)
			{
				echo(" ".$result[$i]);
			}
			echo("\n");
		}
		if ($count >= $n)
		{
			return;
		}
		else
		{
			for ($i = $start + 1; $i <= $n; ++$i)
			{
				// Collect elements 
				$result[$count] = $i;
				$this->subSequences($arr, 
                                    $result, 
                                    $i, 
                                    $count + 1, 
                                    $product * $i,
                                    $n, 
                                    $k);
			}
		}
	}
	// Handles the request to find resultant subsequences
	public	function findProductSequence($arr, $n, $k)
	{
		// Auxiliary array which is collect result
		$result = array_fill(0, $n, 0);
		$this->subSequences($arr, $result, 0, 0, 1, $n, $k);
	}
}

function main()
{
	$task = new Combination();
	$arr = array(1, 2, 3, 4);
	$n = count($arr);
	// Product
	$k = 6;
	// Test 
	$task->findProductSequence($arr, $n, $k);
}
main();

Output

 1
 1 2
 1 2 3
 1 3
 1 4
 2
 2 3
 3
 4
// Node JS program for
// Find all subsequences whose product is less than k in array
class Combination
{
	subSequences(arr, result, start, count, product, n, k)
	{
		if (product <= k)
		{
			for (var i = 0; i < count; ++i)
			{
				process.stdout.write(" " + result[i]);
			}
			process.stdout.write("\n");
		}
		if (count >= n)
		{
			return;
		}
		else
		{
			for (var i = start + 1; i <= n; ++i)
			{
				// Collect elements 
				result[count] = i;
				this.subSequences(arr, result, i, 
                                  count + 1, 
                                  product * i, 
                                  n, k);
			}
		}
	}
	// Handles the request to find resultant subsequences
	findProductSequence(arr, n, k)
	{
		// Auxiliary array which is collect result
		var result = Array(n).fill(0);
		this.subSequences(arr, result, 0, 0, 1, n, k);
	}
}

function main()
{
	var task = new Combination();
	var arr = [1, 2, 3, 4];
	var n = arr.length;
	// Product
	var k = 6;
	// Test 
	task.findProductSequence(arr, n, k);
}
main();

Output

 1
 1 2
 1 2 3
 1 3
 1 4
 2
 2 3
 3
 4
#  Python 3 program for
#  Find all subsequences whose product is less than k in array
class Combination :
	def subSequences(self, arr, result, start, 
                     count, product, n, k) :
		if (product <= k) :
			i = 0
			while (i < count) :
				print(" ", result[i], end = "")
				i += 1
			
			print(end = "\n")
		
		if (count >= n) :
			return
		else :
			i = start + 1
			while (i <= n) :
				#  Collect elements 
				result[count] = i
				self.subSequences(arr, result, i, 
                                  count + 1, 
                                  product * i, n, k)
				i += 1
			
		
	
	#  Handles the request to find resultant subsequences
	def findProductSequence(self, arr, n, k) :
		#  Auxiliary list which is collect result
		result = [0] * (n)
		self.subSequences(arr, result, 0, 0, 1, n, k)
	

def main() :
	task = Combination()
	arr = [1, 2, 3, 4]
	n = len(arr)
	#  Product
	k = 6
	#  Test 
	task.findProductSequence(arr, n, k)

if __name__ == "__main__": main()

Output

  1
  1  2
  1  2  3
  1  3
  1  4
  2
  2  3
  3
  4
#  Ruby program for
#  Find all subsequences whose product is less than k in array
class Combination 
	def subSequences(arr, result, start, 
                     count, product, n, k) 
		if (product <= k) 
			i = 0
			while (i < count) 
				print(" ", result[i])
				i += 1
			end

			print("\n")
		end

		if (count >= n) 
			return
		else
 
			i = start + 1
			while (i <= n) 
				#  Collect elements 
				result[count] = i
				self.subSequences(arr, result, 
                                  i, count + 1, 
                                  product * i, n, k)
				i += 1
			end

		end

	end

	#  Handles the request to find resultant subsequences
	def findProductSequence(arr, n, k) 
		#  Auxiliary array which is collect result
		result = Array.new(n) {0}
		self.subSequences(arr, result, 0, 0, 1, n, k)
	end

end

def main() 
	task = Combination.new()
	arr = [1, 2, 3, 4]
	n = arr.length
	#  Product
	k = 6
	#  Test 
	task.findProductSequence(arr, n, k)
end

main()

Output

 1
 1 2
 1 2 3
 1 3
 1 4
 2
 2 3
 3
 4

// Scala program for
// Find all subsequences whose product is less than k in array
class Combination()
{
	def subSequences(arr: Array[Int], 
      result: Array[Int], 
        start: Int, 
          count: Int, 
            product: Int, 
              n: Int, 
                k: Int): Unit = {
		if (product <= k)
		{
			var i: Int = 0;
			while (i < count)
			{
				print(" " + result(i));
				i += 1;
			}
			print("\n");
		}
		if (count >= n)
		{
			return;
		}
		else
		{
			var i: Int = start + 1;
			while (i <= n)
			{
				// Collect elements 
				result(count) = i;
				subSequences(arr, result, i, 
                             count + 1, 
                             product * i, n, k);
				i += 1;
			}
		}
	}
	// Handles the request to find resultant subsequences
	def findProductSequence(arr: Array[Int], 
      			n: Int, k: Int): Unit = {
		// Auxiliary array which is collect result
		var result: Array[Int] = Array.fill[Int](n)(0);
		subSequences(arr, result, 0, 0, 1, n, k);
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: Combination = new Combination();
		var arr: Array[Int] = Array(1, 2, 3, 4);
		var n: Int = arr.length;
		// Product
		var k: Int = 6;
		// Test 
		task.findProductSequence(arr, n, k);
	}
}

Output

 1
 1 2
 1 2 3
 1 3
 1 4
 2
 2 3
 3
 4
import Foundation;
// Swift 4 program for
// Find all subsequences whose product is less than k in array
class Combination
{
	func subSequences(_ arr: [Int], 
  	  _ result: inout[Int], _ start: Int, 
  	  _ count: Int, _ product: Int, 
      _ n: Int, _ k: Int)
	{
		if (product <= k)
		{
			var i: Int = 0;
			while (i < count)
			{
				print(" ", result[i], terminator: "");
				i += 1;
			}
			print(terminator: "\n");
		}
		if (count >= n)
		{
			return;
		}
		else
		{
			var i: Int = start + 1;
			while (i <= n)
			{
				// Collect elements 
				result[count] = i;
				self.subSequences(arr, &result, 
                                  i, count + 1, 
                                  product * i, 
                                  n, k);
				i += 1;
			}
		}
	}
	// Handles the request to find resultant subsequences
	func findProductSequence(_ arr: [Int], _ n: Int, _ k: Int)
	{
		// Auxiliary array which is collect result
		var result: [Int] = Array(repeating: 0, count: n);
		self.subSequences(arr, &result, 0, 0, 1, n, k);
	}
}
func main()
{
	let task: Combination = Combination();
	let arr: [Int] = [1, 2, 3, 4];
	let n: Int = arr.count;
	// Product
	let k: Int = 6;
	// Test 
	task.findProductSequence(arr, n, k);
}
main();

Output

  1
  1  2
  1  2  3
  1  3
  1  4
  2
  2  3
  3
  4
// Kotlin program for
// Find all subsequences whose product is less than k in array
class Combination
{
	fun subSequences(arr: Array < Int > , 
                      result: Array < Int > , 
                      start: Int, count: Int, 
                      product: Int, 
                      n: Int, 
                      k: Int): Unit
	{
		if (product <= k)
		{
			var i: Int = 0;
			while (i < count)
			{
				print(" " + result[i]);
				i += 1;
			}
			print("\n");
		}
		if (count >= n)
		{
			return;
		}
		else
		{
			var i: Int = start + 1;
			while (i <= n)
			{
				// Collect elements 
				result[count] = i;
				this.subSequences(arr, 
                                  result, i, 
                                  count + 1, 
                                  product * i,
                                  n, 
                                  k);
				i += 1;
			}
		}
	}
	// Handles the request to find resultant subsequences
	fun findProductSequence(arr: Array < Int > , 
                            n: Int, k: Int): Unit
	{
		// Auxiliary array which is collect result
		var result: Array < Int > = Array(n)
		{
			0
		};
		this.subSequences(arr, result, 0, 0, 1, n, k);
	}
}
fun main(args: Array < String > ): Unit
{
	val task: Combination = Combination();
	val arr: Array < Int > = arrayOf(1, 2, 3, 4);
	val n: Int = arr.count();
	// Product
	val k: Int = 6;
	// Test 
	task.findProductSequence(arr, n, k);
}

Output

 1
 1 2
 1 2 3
 1 3
 1 4
 2
 2 3
 3
 4

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





Categories
Relative Post