Posted on by Kalkicode
Code Backtracking

Find all four elements that sum to a given value

Here given code implementation process.

``````// C Program
// Find all four elements that sum to a given value
#include <stdio.h>

void findSum(int arr[],
int result[],
int start,
int index,
int num,
int sum,
int n)
{
if (index == 4 && sum == num)
{
// Display calculated result
printf("\n [ ");
for (int i = 0; i < index; ++i)
{
if (i != 0)
{
printf(" + ");
}
printf("%d", result[i]);
}
printf(" ] = %d ", num);
return;
}
if (index >= 4)
{
return;
}
for (int i = start; i < n; ++i)
{
// Collect resultant element
result[index] = arr[i];
// Find combination of resultant number using recursion
findSum(arr, result, i + 1, index + 1, num, sum + arr[i], n);
}
}
void findGivenSum(int arr[], int n, int num)
{
printf("\n Array :");
// Given array
for (int i = 0; i < n; ++i)
{
printf("  %d", arr[i]);
}
if (n > 3)
{
// This is collecting resultant element
int result[4];
// Find solution
findSum(arr, result, 0, 0, num, 0, n);
}
else
{
printf("\n Less than 4 elements are in this array \n");
}
}
int main()
{
// Array of integer element
int arr[] = {
5 , 1 , 6 , 8 , 2 , 3 , 9 , 13 , 10
};
// Get the length of array
int n = sizeof(arr) / sizeof(arr[0]);
int num = 20;
findGivenSum(arr, n, num);
return 0;
}``````

Output

`````` Array :  5  1  6  8  2  3  9  13  10
[ 5 + 1 + 6 + 8 ] = 20
[ 5 + 2 + 3 + 10 ] = 20
[ 1 + 6 + 3 + 10 ] = 20
[ 1 + 8 + 2 + 9 ] = 20
[ 6 + 2 + 3 + 9 ] = 20``````
``````// Java program for
// Find all four elements that sum to a given value
public class SubSetSum
{
public void findSum(
int[] arr,
int[] result,
int start, int index, int num, int sum, int n)
{
if (index == 4 && sum == num)
{
// Display calculated result
System.out.print("\n [ ");
for (int i = 0; i < index; ++i)
{
if (i != 0)
{
System.out.print(" + ");
}
System.out.print(result[i]);
}
System.out.print(" ] = " + num);
return;
}
if (index >= 4)
{
return;
}
for (int i = start; i < n; ++i)
{
// Collect resultant element
result[index] = arr[i];
// Find combination of resultant number using recursion
findSum(arr, result, i + 1,
index + 1, num, sum + arr[i], n);
}
}
public void findGivenSum(int[] arr, int n, int num)
{
System.out.print("\n Array :");
// Given array
for (int i = 0; i < n; ++i)
{
System.out.print(" " + arr[i]);
}
if (n > 3)
{
// This is collecting resultant element
int[] result = new int[4];
// Find solution
findSum(arr, result, 0, 0, num, 0, n);
}
else
{
System.out.print("\n Less than 4 elements are in this array \n");
}
}
public static void main(String[] args)
{
// Array of integer element
int[] arr = {
5 , 1 , 6 , 8 , 2 , 3 , 9 , 13 , 10
};
// Get the length of array
int n = arr.length;
int num = 20;
}
}``````

Output

`````` Array : 5 1 6 8 2 3 9 13 10
[ 5 + 1 + 6 + 8 ] = 20
[ 5 + 2 + 3 + 10 ] = 20
[ 1 + 6 + 3 + 10 ] = 20
[ 1 + 8 + 2 + 9 ] = 20
[ 6 + 2 + 3 + 9 ] = 20``````
``````// Include header file
#include <iostream>

using namespace std;
// C++ program for
// Find all four elements that sum to a given value
class SubSetSum
{
public: void findSum(int arr[],
int result[], int start, int index,
int num, int sum, int n)
{
if (index == 4 && sum == num)
{
// Display calculated result
cout << "\n [ ";
for (int i = 0; i < index; ++i)
{
if (i != 0)
{
cout << " + ";
}
cout << result[i];
}
cout << " ] = " << num;
return;
}
if (index >= 4)
{
return;
}
for (int i = start; i < n; ++i)
{
// Collect resultant element
result[index] = arr[i];
// Find combination of resultant number using recursion
this->findSum(arr, result, i + 1,
index + 1, num,
sum + arr[i], n);
}
}
void findGivenSum(int arr[], int n, int num)
{
cout << "\n Array :";
// Given array
for (int i = 0; i < n; ++i)
{
cout << " " << arr[i];
}
if (n > 3)
{
// This is collecting resultant element
int result[4];
// Find solution
this->findSum(arr, result, 0, 0, num, 0, n);
}
else
{
cout << "\n Less than 4 elements are in this array \n";
}
}
};
int main()
{
// Array of integer element
int arr[] = {
5 , 1 , 6 , 8 , 2 , 3 , 9 , 13 , 10
};
// Get the length of array
int n = sizeof(arr) / sizeof(arr[0]);
int num = 20;
return 0;
}``````

Output

`````` Array : 5 1 6 8 2 3 9 13 10
[ 5 + 1 + 6 + 8 ] = 20
[ 5 + 2 + 3 + 10 ] = 20
[ 1 + 6 + 3 + 10 ] = 20
[ 1 + 8 + 2 + 9 ] = 20
[ 6 + 2 + 3 + 9 ] = 20``````
``````// Include namespace system
using System;
// Csharp program for
// Find all four elements that sum to a given value
public class SubSetSum
{
public void findSum(int[] arr,
int[] result, int start,
int index, int num,
int sum, int n)
{
if (index == 4 && sum == num)
{
// Display calculated result
Console.Write("\n [ ");
for (int i = 0; i < index; ++i)
{
if (i != 0)
{
Console.Write(" + ");
}
Console.Write(result[i]);
}
Console.Write(" ] = " + num);
return;
}
if (index >= 4)
{
return;
}
for (int i = start; i < n; ++i)
{
// Collect resultant element
result[index] = arr[i];
// Find combination of resultant number using recursion
this.findSum(arr, result, i + 1, index + 1,
num, sum + arr[i], n);
}
}
public void findGivenSum(int[] arr, int n, int num)
{
Console.Write("\n Array :");
// Given array
for (int i = 0; i < n; ++i)
{
Console.Write(" " + arr[i]);
}
if (n > 3)
{
// This is collecting resultant element
int[] result = new int[4];
// Find solution
this.findSum(arr, result, 0, 0, num, 0, n);
}
else
{
Console.Write("\n Less than 4 elements are in this array \n");
}
}
public static void Main(String[] args)
{
// Array of integer element
int[] arr = {
5 , 1 , 6 , 8 , 2 , 3 , 9 , 13 , 10
};
// Get the length of array
int n = arr.Length;
int num = 20;
}
}``````

Output

`````` Array : 5 1 6 8 2 3 9 13 10
[ 5 + 1 + 6 + 8 ] = 20
[ 5 + 2 + 3 + 10 ] = 20
[ 1 + 6 + 3 + 10 ] = 20
[ 1 + 8 + 2 + 9 ] = 20
[ 6 + 2 + 3 + 9 ] = 20``````
``````package main
import "fmt"
// Go program for
// Find all four elements that sum to a given value
type SubSetSum struct {}
func getSubSetSum() * SubSetSum {
var me *SubSetSum = &SubSetSum {}
return me
}
func(this SubSetSum) findSum(arr[] int,
result[] int, start int, index int,
num int, sum int, n int) {
if index == 4 && sum == num {
// Display calculated result
fmt.Print("\n [ ")
for i := 0 ; i < index ; i++ {
if i != 0 {
fmt.Print(" + ")
}
fmt.Print(result[i])
}
fmt.Print(" ] = ", num)
return
}
if index >= 4 {
return
}
for i := start ; i < n ; i++ {
// Collect resultant element
result[index] = arr[i]
// Find combination of resultant
// number using recursion
this.findSum(arr, result, i + 1,
index + 1, num, sum + arr[i], n)
}
}
func(this SubSetSum) findGivenSum(arr[] int,
n int, num int) {
fmt.Print("\n Array :")
// Given array
for i := 0 ; i < n ; i++ {
fmt.Print(" ", arr[i])
}
if n > 3 {
// This is collecting resultant element
var result = make([] int, 4)
// Find solution
this.findSum(arr, result, 0, 0, num, 0, n)
} else {
fmt.Print("\n Less than 4 elements are in this array \n")
}
}
func main() {
var task * SubSetSum = getSubSetSum()
// Array of integer element
var arr = [] int {
5,
1,
6,
8,
2,
3,
9,
13,
10,
}
// Get the length of array
var n int = len(arr)
var num int = 20
}``````

Output

`````` Array : 5 1 6 8 2 3 9 13 10
[ 5 + 1 + 6 + 8 ] = 20
[ 5 + 2 + 3 + 10 ] = 20
[ 1 + 6 + 3 + 10 ] = 20
[ 1 + 8 + 2 + 9 ] = 20
[ 6 + 2 + 3 + 9 ] = 20``````
``````<?php
// Php program for
// Find all four elements that sum to a given value
class SubSetSum
{
public	function findSum(\$arr, \$result, \$start,
\$index, \$num, \$sum, \$n)
{
if (\$index == 4 && \$sum == \$num)
{
// Display calculated result
echo("\n [ ");
for (\$i = 0; \$i < \$index; ++\$i)
{
if (\$i != 0)
{
echo(". ");
}
echo(\$result[\$i]);
}
echo(" ] = ".\$num);
return;
}
if (\$index >= 4)
{
return;
}
for (\$i = \$start; \$i < \$n; ++\$i)
{
// Collect resultant element
\$result[\$index] = \$arr[\$i];
// Find combination of resultant number using recursion
\$this->findSum(\$arr, \$result, \$i + 1,
\$index + 1, \$num, \$sum + \$arr[\$i], \$n);
}
}
public	function findGivenSum(\$arr, \$n, \$num)
{
echo("\n Array :");
// Given array
for (\$i = 0; \$i < \$n; ++\$i)
{
echo(" ".\$arr[\$i]);
}
if (\$n > 3)
{
// This is collecting resultant element
\$result = array_fill(0, 4, 0);
// Find solution
\$this->findSum(\$arr, \$result, 0, 0, \$num, 0, \$n);
}
else
{
echo("\n Less than 4 elements are in this array \n");
}
}
}

function main()
{
// Array of integer element
\$arr = array(5, 1, 6, 8, 2, 3, 9, 13, 10);
// Get the length of array
\$n = count(\$arr);
\$num = 20;
}
main();``````

Output

`````` Array : 5 1 6 8 2 3 9 13 10
[ 5. 1. 6. 8 ] = 20
[ 5. 2. 3. 10 ] = 20
[ 1. 6. 3. 10 ] = 20
[ 1. 8. 2. 9 ] = 20
[ 6. 2. 3. 9 ] = 20``````
``````// Node JS program for
// Find all four elements that sum to a given value
class SubSetSum
{
findSum(arr, result, start, index, num, sum, n)
{
if (index == 4 && sum == num)
{
// Display calculated result
process.stdout.write("\n [ ");
for (var i = 0; i < index; ++i)
{
if (i != 0)
{
process.stdout.write(" + ");
}
process.stdout.write("" + result[i]);
}
process.stdout.write(" ] = " + num);
return;
}
if (index >= 4)
{
return;
}
for (var i = start; i < n; ++i)
{
// Collect resultant element
result[index] = arr[i];
// Find combination of resultant number using recursion
this.findSum(arr, result, i + 1, index + 1, num, sum + arr[i], n);
}
}
findGivenSum(arr, n, num)
{
process.stdout.write("\n Array :");
// Given array
for (var i = 0; i < n; ++i)
{
process.stdout.write(" " + arr[i]);
}
if (n > 3)
{
// This is collecting resultant element
var result = Array(4).fill(0);
// Find solution
this.findSum(arr, result, 0, 0, num, 0, n);
}
else
{
process.stdout.write("\n Less than 4 elements are in this array \n");
}
}
}

function main()
{
// Array of integer element
var arr = [5, 1, 6, 8, 2, 3, 9, 13, 10];
// Get the length of array
var n = arr.length;
var num = 20;
}
main();``````

Output

`````` Array : 5 1 6 8 2 3 9 13 10
[ 5 + 1 + 6 + 8 ] = 20
[ 5 + 2 + 3 + 10 ] = 20
[ 1 + 6 + 3 + 10 ] = 20
[ 1 + 8 + 2 + 9 ] = 20
[ 6 + 2 + 3 + 9 ] = 20``````
``````#  Python 3 program for
#  Find all four elements that sum to a given value
class SubSetSum :
def findSum(self, arr, result, start,
index, num, sum, n) :
if (index == 4 and sum == num) :
#  Display calculated result
print("\n [ ", end = "")
i = 0
while (i < index) :
if (i != 0) :
print(" + ", end = "")

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

print(" ] = ", num, end = "")
return

if (index >= 4) :
return

i = start
while (i < n) :
#  Collect resultant element
result[index] = arr[i]
#  Find combination of resultant number using recursion
self.findSum(arr, result, i + 1, index + 1,
num, sum + arr[i], n)
i += 1

def findGivenSum(self, arr, n, num) :
print("\n Array :", end = "")
i = 0
#  Given list
while (i < n) :
print(" ", arr[i], end = "")
i += 1

if (n > 3) :
#  This is collecting resultant element
result = [0] * (4)
#  Find solution
self.findSum(arr, result, 0, 0, num, 0, n)
else :
print("\n Less than 4 elements are in this array ")

def main() :
#  Array of integer element
arr = [5, 1, 6, 8, 2, 3, 9, 13, 10]
#  Get the length of list
n = len(arr)
num = 20

if __name__ == "__main__": main()``````

Output

`````` Array :  5  1  6  8  2  3  9  13  10
[ 5 + 1 + 6 + 8 ] =  20
[ 5 + 2 + 3 + 10 ] =  20
[ 1 + 6 + 3 + 10 ] =  20
[ 1 + 8 + 2 + 9 ] =  20
[ 6 + 2 + 3 + 9 ] =  20``````
``````#  Ruby program for
#  Find all four elements that sum to a given value
class SubSetSum
def findSum(arr, result, start, index, num, sum, n)
if (index == 4 && sum == num)
#  Display calculated result
print("\n [ ")
i = 0
while (i < index)
if (i != 0)
print(" + ")
end

print(result[i])
i += 1
end

print(" ] = ", num)
return
end

if (index >= 4)
return
end

i = start
while (i < n)
#  Collect resultant element
result[index] = arr[i]
#  Find combination of resultant number using recursion
self.findSum(arr, result, i + 1,
index + 1, num, sum + arr[i], n)
i += 1
end

end

def findGivenSum(arr, n, num)
print("\n Array :")
i = 0
#  Given array
while (i < n)
print(" ", arr[i])
i += 1
end

if (n > 3)
#  This is collecting resultant element
result = Array.new(4) {0}
#  Find solution
self.findSum(arr, result, 0, 0, num, 0, n)
else

print("\n Less than 4 elements are in this array \n")
end

end

end

def main()
#  Array of integer element
arr = [5, 1, 6, 8, 2, 3, 9, 13, 10]
#  Get the length of array
n = arr.length
num = 20
end

main()``````

Output

`````` Array : 5 1 6 8 2 3 9 13 10
[ 5 + 1 + 6 + 8 ] = 20
[ 5 + 2 + 3 + 10 ] = 20
[ 1 + 6 + 3 + 10 ] = 20
[ 1 + 8 + 2 + 9 ] = 20
[ 6 + 2 + 3 + 9 ] = 20``````
``````// Scala program for
// Find all four elements that sum to a given value
class SubSetSum()
{
def findSum(arr: Array[Int], result: Array[Int],
start: Int, index: Int, num: Int,
sum: Int, n: Int): Unit = {
if (index == 4 && sum == num)
{
// Display calculated result
print("\n [ ");
var i: Int = 0;
while (i < index)
{
if (i != 0)
{
print(" + ");
}
print(result(i));
i += 1;
}
print(" ] = " + num);
return;
}
if (index >= 4)
{
return;
}
var i: Int = start;
while (i < n)
{
// Collect resultant element
result(index) = arr(i);
// Find combination of resultant number using recursion
findSum(arr, result, i + 1, index + 1,
num, sum + arr(i), n);
i += 1;
}
}
def findGivenSum(arr: Array[Int],
n: Int, num: Int): Unit = {
print("\n Array :");
var i: Int = 0;
// Given array
while (i < n)
{
print(" " + arr(i));
i += 1;
}
if (n > 3)
{
// This is collecting resultant element
var result: Array[Int] = Array.fill[Int](4)(0);
// Find solution
findSum(arr, result, 0, 0, num, 0, n);
}
else
{
print("\n Less than 4 elements are in this array \n");
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: SubSetSum = new SubSetSum();
// Array of integer element
var arr: Array[Int] = Array(5, 1, 6, 8, 2, 3, 9, 13, 10);
// Get the length of array
var n: Int = arr.length;
var num: Int = 20;
}
}``````

Output

`````` Array : 5 1 6 8 2 3 9 13 10
[ 5 + 1 + 6 + 8 ] = 20
[ 5 + 2 + 3 + 10 ] = 20
[ 1 + 6 + 3 + 10 ] = 20
[ 1 + 8 + 2 + 9 ] = 20
[ 6 + 2 + 3 + 9 ] = 20``````
``````import Foundation;
// Swift 4 program for
// Find all four elements that sum to a given value
class SubSetSum
{
func findSum(_ arr: [Int], _ result: inout[Int],
_ start: Int, _ index: Int, _ num: Int, _ sum: Int, _ n: Int)
{
if (index == 4 && sum == num)
{
// Display calculated result
print("\n [ ", terminator: "");
var i: Int = 0;
while (i < index)
{
if (i  != 0)
{
print(" + ", terminator: "");
}
print(result[i], terminator: "");
i += 1;
}
print(" ] = ", num, terminator: "");
return;
}
if (index >= 4)
{
return;
}
var i: Int = start;
while (i < n)
{
// Collect resultant element
result[index] = arr[i];
// Find combination of resultant number using recursion
self.findSum(arr, &result, i + 1,
index + 1, num, sum + arr[i], n);
i += 1;
}
}
func findGivenSum(_ arr: [Int], _ n: Int, _ num: Int)
{
print("\n Array :", terminator: "");
var i: Int = 0;
// Given array
while (i < n)
{
print(" ", arr[i], terminator: "");
i += 1;
}
if (n > 3)
{
// This is collecting resultant element
var result: [Int] = Array(repeating: 0, count: 4);
// Find solution
self.findSum(arr, &result, 0, 0, num, 0, n);
}
else
{
print("\n Less than 4 elements are in this array ");
}
}
}
func main()
{
// Array of integer element
let arr: [Int] = [5, 1, 6, 8, 2, 3, 9, 13, 10];
// Get the length of array
let n: Int = arr.count;
let num: Int = 20;
}
main();``````

Output

`````` Array :  5  1  6  8  2  3  9  13  10
[ 5 + 1 + 6 + 8 ] =  20
[ 5 + 2 + 3 + 10 ] =  20
[ 1 + 6 + 3 + 10 ] =  20
[ 1 + 8 + 2 + 9 ] =  20
[ 6 + 2 + 3 + 9 ] =  20``````
``````// Kotlin program for
// Find all four elements that sum to a given value
class SubSetSum
{
fun findSum(arr: Array < Int > ,
result: Array < Int > , start: Int,
index: Int, num: Int, sum: Int, n: Int): Unit
{
if (index == 4 && sum == num)
{
// Display calculated result
print("\n [ ");
var i: Int = 0;
while (i < index)
{
if (i != 0)
{
print(" + ");
}
print(result[i]);
i += 1;
}
print(" ] = " + num);
return;
}
if (index >= 4)
{
return;
}
var i: Int = start;
while (i < n)
{
// Collect resultant element
result[index] = arr[i];
// Find combination of resultant number using recursion
this.findSum(arr, result, i + 1, index + 1, num, sum + arr[i], n);
i += 1;
}
}
fun findGivenSum(arr: Array < Int > , n: Int, num: Int): Unit
{
print("\n Array :");
var i: Int = 0;
// Given array
while (i < n)
{
print(" " + arr[i]);
i += 1;
}
if (n > 3)
{
// This is collecting resultant element
val result: Array < Int > = Array(4)
{
0
};
// Find solution
this.findSum(arr, result, 0, 0, num, 0, n);
}
else
{
print("\n Less than 4 elements are in this array \n");
}
}
}
fun main(args: Array < String > ): Unit
{
// Array of integer element
val arr: Array < Int > = arrayOf(5, 1, 6, 8, 2, 3, 9, 13, 10);
// Get the length of array
val n: Int = arr.count();
val num: Int = 20;
}``````

Output

`````` Array : 5 1 6 8 2 3 9 13 10
[ 5 + 1 + 6 + 8 ] = 20
[ 5 + 2 + 3 + 10 ] = 20
[ 1 + 6 + 3 + 10 ] = 20
[ 1 + 8 + 2 + 9 ] = 20
[ 6 + 2 + 3 + 9 ] = 20``````

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.

Categories
Relative Post