Posted on by Kalkicode
Code Backtracking

Find Subset sum which divisible by k

Here given code implementation process.

// Java program for
// Find Subset sum which divisible by k
public class Combination
{
	public void printData(int[] arr, int size)
	{
		System.out.print("\n Array elements \n");
		for (int i = 0; i < size; ++i)
		{
			System.out.print(" " + arr[i]);
		}
		System.out.print("\n");
	}
	// Find the subset sum in given array
	public void subsetSum(int[] arr, 
                          int[] result, 
      int size, 
        int i, 
          int j, 
            int sum, 
              int k)
	{
		if (i == size)
		{
			if ((j > 0) && sum % k == 0)
			{
				System.out.print(" (");
				for (int l = 0; l < j; ++l)
				{
					if (l != 0)
					{
						System.out.print("+");
					}
					System.out.print(" " + result[l] + " ");
				}
				System.out.print(") % " + k + " = 0\n");
			}
			return;
		}
		// Recursively, find subset sum
		subsetSum(arr, 
                  result, 
                  size, 
                  i + 1, 
                  j, 
                  sum, 
                  k);
		result[j] = arr[i];
		subsetSum(arr, 
                  result, 
                  size, 
                  i + 1, 
                  j + 1, 
                  sum + arr[i], 
                  k);
	}
	public void findSubset(int[] arr, int size, int k)
	{
		// Auxiliary array which is collect result
		int[] result = new int[size];
		printData(arr, size);
		System.out.print(" Divisible k : " + k);
		System.out.print("\n Result \n");
		subsetSum(arr, result, size, 0, 0, 0, k);
	}
	public static void main(String[] args)
	{
		Combination task = new Combination();
		int[] arr1 = {
			4 , 6 , 8 , 2 , 3
		};
		// Get the number of element in array
		int size = arr1.length;
		/*
		    4 6 8 2 3
		    Divisible k : 6
		    Result 
		    ( 6 ) % 6 = 0
		    ( 4 + 2 ) % 6 = 0
		    ( 4 + 8 ) % 6 = 0
		    ( 4 + 6 + 2 ) % 6 = 0
		    ( 4 + 6 + 8 ) % 6 = 0

		*/
		task.findSubset(arr1, size, 6);
	}
}

Output

 Array elements
 4 6 8 2 3
 Divisible k : 6
 Result
 ( 6 ) % 6 = 0
 ( 4 + 2 ) % 6 = 0
 ( 4 + 8 ) % 6 = 0
 ( 4 + 6 + 2 ) % 6 = 0
 ( 4 + 6 + 8 ) % 6 = 0
/*
    C Program 
    Find Subset sum which divisible by k
*/
#include <stdio.h>

void printData(int arr[], int size)
{
	printf("\n Array elements \n");
	for (int i = 0; i < size; ++i)
	{
		printf(" %d", arr[i]);
	}
	printf("\n");
}
// Find the subset sum in given array
void subsetSum(int arr[], int result[], 
  			   int size, int i, 
               int j, 
               int sum, 
               int k)
{
	if (i == size)
	{
		if ((j > 0) && sum % k == 0)
		{
			printf(" (");
			for (int i = 0; i < j; ++i)
			{
				if (i != 0)
				{
					printf("+");
				}
				printf(" %d ", result[i]);
			}
			printf(") %% %d = 0\n", k);
		}
		return;
	}
	// Recursively, find subset sum
	subsetSum(arr, result, size, i + 1, j, sum, k);
	result[j] = arr[i];
	subsetSum(arr, result, size, i + 1, j + 1, sum + arr[i], k);
}
void findSubset(int arr[], int size, int k)
{
	// Auxiliary array which is collect result
	int result[size];
	printData(arr, size);
	printf(" Divisible k : %d", k);
	printf("\n Result \n");
	subsetSum(arr, result, size, 0, 0, 0, k);
}
int main(int argc, char const *argv[])
{
	int arr1[] = {
		4 , 6 , 8 , 2 , 3
	};
	// Get the number of element in array
	int size = sizeof(arr1) / sizeof(arr1[0]);
	/*
	    4 6 8 2 3
	    Divisible k : 6
	    Result 
	    ( 6 ) % 6 = 0
	    ( 4 + 2 ) % 6 = 0
	    ( 4 + 8 ) % 6 = 0
	    ( 4 + 6 + 2 ) % 6 = 0
	    ( 4 + 6 + 8 ) % 6 = 0

	*/
	findSubset(arr1, size, 6);
	return 0;
}

Output

 Array elements
 4 6 8 2 3
 Divisible k : 6
 Result
 ( 6 ) % 6 = 0
 ( 4 + 2 ) % 6 = 0
 ( 4 + 8 ) % 6 = 0
 ( 4 + 6 + 2 ) % 6 = 0
 ( 4 + 6 + 8 ) % 6 = 0
// Include header file
#include <iostream>

using namespace std;
// C++ program for
// Find Subset sum which divisible by k
class Combination
{
	public: void printData(int arr[], int size)
	{
		cout << "\n Array elements \n";
		for (int i = 0; i < size; ++i)
		{
			cout << " " << arr[i];
		}
		cout << "\n";
	}
	// Find the subset sum in given array
	void subsetSum(int arr[], int result[], 
      int size, int i, 
        int j, 
          int sum, 
            int k)
	{
		if (i == size)
		{
			if ((j > 0) && sum % k == 0)
			{
				cout << " (";
				for (int l = 0; l < j; ++l)
				{
					if (l != 0)
					{
						cout << "+";
					}
					cout << " " << result[l] << " ";
				}
				cout << ") % " << k << " = 0\n";
			}
			return;
		}
		// Recursively, find subset sum
		this->subsetSum(arr, result, 
                        size, i + 1, 
                        j, sum, k);
		result[j] = arr[i];
		this->subsetSum(arr, result, 
                        size, i + 1, 
                        j + 1, 
                        sum + arr[i], 
                        k);
	}
	void findSubset(int arr[], int size, int k)
	{
		// Auxiliary array which is collect result
		int result[size];
		this->printData(arr, size);
		cout << " Divisible k : " << k;
		cout << "\n Result \n";
		this->subsetSum(arr, result, size, 0, 0, 0, k);
	}
};
int main()
{
	Combination *task = new Combination();
	int arr1[] = {
		4 , 6 , 8 , 2 , 3
	};
	// Get the number of element in array
	int size = sizeof(arr1) / sizeof(arr1[0]);
	/*
	    4 6 8 2 3
	    Divisible k : 6
	    Result 
	    ( 6 ) % 6 = 0
	    ( 4 + 2 ) % 6 = 0
	    ( 4 + 8 ) % 6 = 0
	    ( 4 + 6 + 2 ) % 6 = 0
	    ( 4 + 6 + 8 ) % 6 = 0
	*/
	task->findSubset(arr1, size, 6);
	return 0;
}

Output

 Array elements
 4 6 8 2 3
 Divisible k : 6
 Result
 ( 6 ) % 6 = 0
 ( 4 + 2 ) % 6 = 0
 ( 4 + 8 ) % 6 = 0
 ( 4 + 6 + 2 ) % 6 = 0
 ( 4 + 6 + 8 ) % 6 = 0
// Include namespace system
using System;
// Csharp program for
// Find Subset sum which divisible by k
public class Combination
{
	public void printData(int[] arr, int size)
	{
		Console.Write("\n Array elements \n");
		for (int i = 0; i < size; ++i)
		{
			Console.Write(" " + arr[i]);
		}
		Console.Write("\n");
	}
	// Find the subset sum in given array
	public void subsetSum(int[] arr, 
                          int[] result, 
      int size, 
        int i, 
          int j, 
            int sum, 
              int k)
	{
		if (i == size)
		{
			if ((j > 0) && sum % k == 0)
			{
				Console.Write(" (");
				for (int l = 0; l < j; ++l)
				{
					if (l != 0)
					{
						Console.Write("+");
					}
					Console.Write(" " + result[l] + " ");
				}
				Console.Write(") % " + k + " = 0\n");
			}
			return;
		}
		// Recursively, find subset sum
		this.subsetSum(arr, result, size, i + 1, j, sum, k);
		result[j] = arr[i];
		this.subsetSum(arr, result, size, i + 1, j + 1, sum + arr[i], k);
	}
	public void findSubset(int[] arr, int size, int k)
	{
		// Auxiliary array which is collect result
		int[] result = new int[size];
		this.printData(arr, size);
		Console.Write(" Divisible k : " + k);
		Console.Write("\n Result \n");
		this.subsetSum(arr, result, size, 0, 0, 0, k);
	}
	public static void Main(String[] args)
	{
		Combination task = new Combination();
		int[] arr1 = {
			4 , 6 , 8 , 2 , 3
		};
		// Get the number of element in array
		int size = arr1.Length;
		/*
		    4 6 8 2 3
		    Divisible k : 6
		    Result 
		    ( 6 ) % 6 = 0
		    ( 4 + 2 ) % 6 = 0
		    ( 4 + 8 ) % 6 = 0
		    ( 4 + 6 + 2 ) % 6 = 0
		    ( 4 + 6 + 8 ) % 6 = 0
		*/
		task.findSubset(arr1, size, 6);
	}
}

Output

 Array elements
 4 6 8 2 3
 Divisible k : 6
 Result
 ( 6 ) % 6 = 0
 ( 4 + 2 ) % 6 = 0
 ( 4 + 8 ) % 6 = 0
 ( 4 + 6 + 2 ) % 6 = 0
 ( 4 + 6 + 8 ) % 6 = 0
package main
import "fmt"
// Go program for
// Find Subset sum which divisible by k
type Combination struct {}
func getCombination() * Combination {
	var me *Combination = &Combination {}
	return me
}
func(this Combination) printData(arr[] int, size int) {
	fmt.Print("\n Array elements \n")
	for i := 0 ; i < size ; i++ {
		fmt.Print(" ", arr[i])
	}
	fmt.Print("\n")
}
// Find the subset sum in given array
func(this Combination) subsetSum(arr[] int, 
	result[] int, size int, 
	i int, j int, sum int, k int) {
	if i == size {
		if (j > 0) && sum % k == 0 {
			fmt.Print(" (")
			for l := 0 ; l < j ; l++ {
				if l != 0 {
					fmt.Print("+")
				}
				fmt.Print(" ", result[l], " ")
			}
			fmt.Print(") % ", k, " = 0\n")
		}
		return
	}
	// Recursively, find subset sum
	this.subsetSum(arr, result, size, 
				  i + 1, j, sum, k)
	result[j] = arr[i]
	this.subsetSum(arr, result, size, 
				  i + 1, j + 1, sum + arr[i], k)
}
func(this Combination) findSubset(arr[] int, 
	size int, k int) {
	// Auxiliary array which is collect result
	var result = make([] int, size)
	this.printData(arr, size)
	fmt.Print(" Divisible k : ", k)
	fmt.Print("\n Result \n")
	this.subsetSum(arr, result, size, 0, 0, 0, k)
}
func main() {
	var task * Combination = getCombination()
	var arr1 = [] int {
		4,
		6,
		8,
		2,
		3,
	}
	// Get the number of element in array
	var size int = len(arr1)
	/*
	    4 6 8 2 3
	    Divisible k : 6
	    Result 
	    ( 6 ) % 6 = 0
	    ( 4 + 2 ) % 6 = 0
	    ( 4 + 8 ) % 6 = 0
	    ( 4 + 6 + 2 ) % 6 = 0
	    ( 4 + 6 + 8 ) % 6 = 0
	*/
	task.findSubset(arr1, size, 6)
}

Output

 Array elements
 4 6 8 2 3
 Divisible k : 6
 Result
 ( 6 ) % 6 = 0
 ( 4 + 2 ) % 6 = 0
 ( 4 + 8 ) % 6 = 0
 ( 4 + 6 + 2 ) % 6 = 0
 ( 4 + 6 + 8 ) % 6 = 0
<?php
// Php program for
// Find Subset sum which divisible by k
class Combination
{
	public	function printData($arr, $size)
	{
		echo("\n Array elements \n");
		for ($i = 0; $i < $size; ++$i)
		{
			echo(" ".$arr[$i]);
		}
		echo("\n");
	}
	// Find the subset sum in given array
	public	function subsetSum($arr, 
                                $result, 
                                $size, 
                                $i, 
                                $j, 
                                $sum, 
                                $k)
	{
		if ($i == $size)
		{
			if (($j > 0) && $sum % $k == 0)
			{
				echo(" (");
				for ($l = 0; $l < $j; ++$l)
				{
					if ($l != 0)
					{
						echo("+");
					}
					echo(" ".$result[$l].
						" ");
				}
				echo(") % ".$k." = 0\n");
			}
			return;
		}
		// Recursively, find subset sum
		$this->subsetSum($arr, 
                         $result, 
                         $size, 
                         $i + 1, 
                         $j, 
                         $sum, 
                         $k);
		$result[$j] = $arr[$i];
		$this->subsetSum($arr, 
                         $result, 
                         $size, 
                         $i + 1, 
                         $j + 1, 
                         $sum + $arr[$i], 
                         $k);
	}
	public	function findSubset($arr, $size, $k)
	{
		// Auxiliary array which is collect result
		$result = array_fill(0, $size, 0);
		$this->printData($arr, $size);
		echo(" Divisible k : ".$k);
		echo("\n Result \n");
		$this->subsetSum($arr, $result, $size, 0, 0, 0, $k);
	}
}

function main()
{
	$task = new Combination();
	$arr1 = array(4, 6, 8, 2, 3);
	// Get the number of element in array
	$size = count($arr1);
	/*
	    4 6 8 2 3
	    Divisible k : 6
	    Result 
	    ( 6 ) % 6 = 0
	    ( 4 + 2 ) % 6 = 0
	    ( 4 + 8 ) % 6 = 0
	    ( 4 + 6 + 2 ) % 6 = 0
	    ( 4 + 6 + 8 ) % 6 = 0
	*/
	$task->findSubset($arr1, $size, 6);
}
main();

Output

 Array elements
 4 6 8 2 3
 Divisible k : 6
 Result
 ( 6 ) % 6 = 0
 ( 4 + 2 ) % 6 = 0
 ( 4 + 8 ) % 6 = 0
 ( 4 + 6 + 2 ) % 6 = 0
 ( 4 + 6 + 8 ) % 6 = 0
// Node JS program for
// Find Subset sum which divisible by k
class Combination
{
	printData(arr, size)
	{
		process.stdout.write("\n Array elements \n");
		for (var i = 0; i < size; ++i)
		{
			process.stdout.write(" " + arr[i]);
		}
		process.stdout.write("\n");
	}
	// Find the subset sum in given array
	subsetSum(arr, result, size, i, j, sum, k)
	{
		if (i == size)
		{
			if ((j > 0) && sum % k == 0)
			{
				process.stdout.write(" (");
				for (var l = 0; l < j; ++l)
				{
					if (l != 0)
					{
						process.stdout.write("+");
					}
					process.stdout.write(" " + result[l] + " ");
				}
				process.stdout.write(") % " + k + " = 0\n");
			}
			return;
		}
		// Recursively, find subset sum
		this.subsetSum(arr, result, size, 
                       i + 1, j, sum, k);
		result[j] = arr[i];
		this.subsetSum(arr, result, size, 
                       i + 1, j + 1, sum + arr[i], k);
	}
	findSubset(arr, size, k)
	{
		// Auxiliary array which is collect result
		var result = Array(size).fill(0);
		this.printData(arr, size);
		process.stdout.write(" Divisible k : " + k);
		process.stdout.write("\n Result \n");
		this.subsetSum(arr, result, size, 0, 0, 0, k);
	}
}

function main()
{
	var task = new Combination();
	var arr1 = [4, 6, 8, 2, 3];
	// Get the number of element in array
	var size = arr1.length;
	/*
	    4 6 8 2 3
	    Divisible k : 6
	    Result 
	    ( 6 ) % 6 = 0
	    ( 4 + 2 ) % 6 = 0
	    ( 4 + 8 ) % 6 = 0
	    ( 4 + 6 + 2 ) % 6 = 0
	    ( 4 + 6 + 8 ) % 6 = 0
	*/
	task.findSubset(arr1, size, 6);
}
main();

Output

 Array elements
 4 6 8 2 3
 Divisible k : 6
 Result
 ( 6 ) % 6 = 0
 ( 4 + 2 ) % 6 = 0
 ( 4 + 8 ) % 6 = 0
 ( 4 + 6 + 2 ) % 6 = 0
 ( 4 + 6 + 8 ) % 6 = 0
#  Python 3 program for
#  Find Subset sum which divisible by k
class Combination :
	def printData(self, arr, size) :
		print("\n Array elements ")
		i = 0
		while (i < size) :
			print(" ", arr[i], end = "")
			i += 1
		
		print(end = "\n")
	
	#  Find the subset sum in given list
	def subsetSum(self, arr, result, size, i, j, sum, k) :
		if (i == size) :
			if ((j > 0) and sum % k == 0) :
				print(" (", end = "")
				l = 0
				while (l < j) :
					if (l != 0) :
						print("+", end = "")
					
					print(" ", result[l] ," ", end = "")
					l += 1
				
				print(") % ", k ," = 0")
			
			return
		
		#  Recursively, find subset sum
		self.subsetSum(arr, result, 
                       size, i + 1, j, sum, k)
		result[j] = arr[i]
		self.subsetSum(arr, result, 
                       size, i + 1, 
                       j + 1, sum + arr[i], k)
	
	def findSubset(self, arr, size, k) :
		#  Auxiliary list which is collect result
		result = [0] * (size)
		self.printData(arr, size)
		print(" Divisible k : ", k, end = "")
		print("\n Result ")
		self.subsetSum(arr, result, size, 0, 0, 0, k)
	

def main() :
	task = Combination()
	arr1 = [4, 6, 8, 2, 3]
	#  Get the number of element in list
	size = len(arr1)
	#    4 6 8 2 3
	#    Divisible k : 6
	#    Result 
	#    ( 6 ) % 6 = 0
	#    ( 4 + 2 ) % 6 = 0
	#    ( 4 + 8 ) % 6 = 0
	#    ( 4 + 6 + 2 ) % 6 = 0
	#    ( 4 + 6 + 8 ) % 6 = 0
	task.findSubset(arr1, size, 6)

if __name__ == "__main__": main()

Output

 Array elements
  4  6  8  2  3
 Divisible k :  6
 Result
 (  6  ) %  6  = 0
 (  4  +  2  ) %  6  = 0
 (  4  +  8  ) %  6  = 0
 (  4  +  6  +  2  ) %  6  = 0
 (  4  +  6  +  8  ) %  6  = 0
#  Ruby program for
#  Find Subset sum which divisible by k
class Combination 
	def printData(arr, size) 
		print("\n Array elements \n")
		i = 0
		while (i < size) 
			print(" ", arr[i])
			i += 1
		end

		print("\n")
	end

	#  Find the subset sum in given array
	def subsetSum(arr, result, size, i, j, sum, k) 
		if (i == size) 
			if ((j > 0) && sum % k == 0) 
				print(" (")
				l = 0
				while (l < j) 
					if (l != 0) 
						print("+")
					end

					print(" ", result[l] ," ")
					l += 1
				end

				print(") % ", k ," = 0\n")
			end

			return
		end

		#  Recursively, find subset sum
		self.subsetSum(arr, result, size, 
                       i + 1, j, sum, k)
		result[j] = arr[i]
		self.subsetSum(arr, result, size, 
                       i + 1, j + 1, sum + arr[i], k)
	end

	def findSubset(arr, size, k) 
		#  Auxiliary array which is collect result
		result = Array.new(size) {0}
		self.printData(arr, size)
		print(" Divisible k : ", k)
		print("\n Result \n")
		self.subsetSum(arr, result, size, 0, 0, 0, k)
	end

end

def main() 
	task = Combination.new()
	arr1 = [4, 6, 8, 2, 3]
	#  Get the number of element in array
	size = arr1.length
	#    4 6 8 2 3
	#    Divisible k : 6
	#    Result 
	#    ( 6 ) % 6 = 0
	#    ( 4 + 2 ) % 6 = 0
	#    ( 4 + 8 ) % 6 = 0
	#    ( 4 + 6 + 2 ) % 6 = 0
	#    ( 4 + 6 + 8 ) % 6 = 0
	task.findSubset(arr1, size, 6)
end

main()

Output

 Array elements 
 4 6 8 2 3
 Divisible k : 6
 Result 
 ( 6 ) % 6 = 0
 ( 4 + 2 ) % 6 = 0
 ( 4 + 8 ) % 6 = 0
 ( 4 + 6 + 2 ) % 6 = 0
 ( 4 + 6 + 8 ) % 6 = 0
// Scala program for
// Find Subset sum which divisible by k
class Combination()
{
	def printData(arr: Array[Int], size: Int): Unit = {
		print("\n Array elements \n");
		var i: Int = 0;
		while (i < size)
		{
			print(" " + arr(i));
			i += 1;
		}
		print("\n");
	}
	// Find the subset sum in given array
	def subsetSum(arr: Array[Int], 
      result: Array[Int], 
        size: Int, i: Int, 
          j: Int, sum: Int, 
            k: Int): Unit = {
		if (i == size)
		{
			if ((j > 0) && sum % k == 0)
			{
				print(" (");
				var l: Int = 0;
				while (l < j)
				{
					if (l != 0)
					{
						print("+");
					}
					print(" " + result(l) + " ");
					l += 1;
				}
				print(") % " + k + " = 0\n");
			}
			return;
		}
		// Recursively, find subset sum
		subsetSum(arr, result, size, 
                  i + 1, j, sum, k);
		result(j) = arr(i);
		subsetSum(arr, result, size, 
                  i + 1, j + 1, sum + arr(i), k);
	}
	def findSubset(arr: Array[Int], size: Int, k: Int): Unit = {
		// Auxiliary array which is collect result
		var result: Array[Int] = Array.fill[Int](size)(0);
		printData(arr, size);
		print(" Divisible k : " + k);
		print("\n Result \n");
		subsetSum(arr, result, size, 0, 0, 0, k);
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: Combination = new Combination();
		var arr1: Array[Int] = Array(4, 6, 8, 2, 3);
		// Get the number of element in array
		var size: Int = arr1.length;
		/*
		    4 6 8 2 3
		    Divisible k : 6
		    Result 
		    ( 6 ) % 6 = 0
		    ( 4 + 2 ) % 6 = 0
		    ( 4 + 8 ) % 6 = 0
		    ( 4 + 6 + 2 ) % 6 = 0
		    ( 4 + 6 + 8 ) % 6 = 0
		*/
		task.findSubset(arr1, size, 6);
	}
}

Output

 Array elements
 4 6 8 2 3
 Divisible k : 6
 Result
 ( 6 ) % 6 = 0
 ( 4 + 2 ) % 6 = 0
 ( 4 + 8 ) % 6 = 0
 ( 4 + 6 + 2 ) % 6 = 0
 ( 4 + 6 + 8 ) % 6 = 0
import Foundation;
// Swift 4 program for
// Find Subset sum which divisible by k
class Combination
{
	func printData(_ arr: [Int], _ size: Int)
	{
		print("\n Array elements ");
		var i: Int = 0;
		while (i < size)
		{
			print(" ", arr[i], terminator: "");
			i += 1;
		}
		print(terminator: "\n");
	}
	// Find the subset sum in given array
	func subsetSum(_ arr: [Int], 
      _ result: inout[Int], 
        _ size: Int, 
          _ i: Int, 
            _ j: Int, 
              _ sum: Int, 
                _ k: Int)
	{
		if (i == size)
		{
			if ((j > 0) && sum % k == 0)
			{
				print(" (", terminator: "");
				var l: Int = 0;
				while (l < j)
				{
					if (l  != 0)
					{
						print("+", terminator: "");
					}
					print(" ", result[l] ," ", terminator: "");
					l += 1;
				}
				print(") % ", k ," = 0");
			}
			return;
		}
		// Recursively, find subset sum
		self.subsetSum(arr, &result, 
                       size, i + 1, j, sum, k);
		result[j] = arr[i];
		self.subsetSum(arr, &result, 
                       size, i + 1, j + 1, sum + arr[i], k);
	}
	func findSubset(_ arr: [Int], _ size: Int, _ k: Int)
	{
		// Auxiliary array which is collect result
		var result: [Int] = Array(repeating: 0, count: size);
		self.printData(arr, size);
		print(" Divisible k : ", k, terminator: "");
		print("\n Result ");
		self.subsetSum(arr, &result, size, 0, 0, 0, k);
	}
}
func main()
{
	let task: Combination = Combination();
	let arr1: [Int] = [4, 6, 8, 2, 3];
	// Get the number of element in array
	let size: Int = arr1.count;
	/*
	    4 6 8 2 3
	    Divisible k : 6
	    Result 
	    ( 6 ) % 6 = 0
	    ( 4 + 2 ) % 6 = 0
	    ( 4 + 8 ) % 6 = 0
	    ( 4 + 6 + 2 ) % 6 = 0
	    ( 4 + 6 + 8 ) % 6 = 0
	*/
	task.findSubset(arr1, size, 6);
}
main();

Output

 Array elements
  4  6  8  2  3
 Divisible k :  6
 Result
 (  6  ) %  6  = 0
 (  4  +  2  ) %  6  = 0
 (  4  +  8  ) %  6  = 0
 (  4  +  6  +  2  ) %  6  = 0
 (  4  +  6  +  8  ) %  6  = 0
// Kotlin program for
// Find Subset sum which divisible by k
class Combination
{
	fun printData(arr: Array < Int > , size: Int): Unit
	{
		print("\n Array elements \n");
		var i: Int = 0;
		while (i < size)
		{
			print(" " + arr[i]);
			i += 1;
		}
		print("\n");
	}
	// Find the subset sum in given array
	fun subsetSum(arr: Array < Int > , 
                  result: Array < Int > , 
                  size: Int, i: Int, 
                  j: Int, sum: Int, 
                  k: Int): Unit
	{
		if (i == size)
		{
			if ((j > 0) && sum % k == 0)
			{
				print(" (");
				var l: Int = 0;
				while (l < j)
				{
					if (l != 0)
					{
						print("+");
					}
					print(" " + result[l] + " ");
					l += 1;
				}
				print(") % " + k + " = 0\n");
			}
			return;
		}
		// Recursively, find subset sum
		this.subsetSum(arr, result, 
                       size, i + 1, j, sum, k);
		result[j] = arr[i];
		this.subsetSum(arr, result, size, 
                       i + 1, j + 1, sum + arr[i], k);
	}
	fun findSubset(arr: Array < Int > , 
                   size: Int, k: Int): Unit
	{
		// Auxiliary array which is collect result
		val result: Array < Int > = Array(size)
		{
			0
		};
		this.printData(arr, size);
		print(" Divisible k : " + k);
		print("\n Result \n");
		this.subsetSum(arr, result, size, 0, 0, 0, k);
	}
}
fun main(args: Array < String > ): Unit
{
	val task: Combination = Combination();
	val arr1: Array < Int > = arrayOf(4, 6, 8, 2, 3);
	// Get the number of element in array
	val size: Int = arr1.count();
	/*
	    4 6 8 2 3
	    Divisible k : 6
	    Result 
	    ( 6 ) % 6 = 0
	    ( 4 + 2 ) % 6 = 0
	    ( 4 + 8 ) % 6 = 0
	    ( 4 + 6 + 2 ) % 6 = 0
	    ( 4 + 6 + 8 ) % 6 = 0
	*/
	task.findSubset(arr1, size, 6);
}

Output

 Array elements
 4 6 8 2 3
 Divisible k : 6
 Result
 ( 6 ) % 6 = 0
 ( 4 + 2 ) % 6 = 0
 ( 4 + 8 ) % 6 = 0
 ( 4 + 6 + 2 ) % 6 = 0
 ( 4 + 6 + 8 ) % 6 = 0

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