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 = 0package 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 = 0import 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
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