Print all subsets with given sum
In this article, we will discuss a C program that prints all subsets of an input array that add up to a given sum. The program uses a recursive approach to generate all possible combinations of elements from the array and checks if their sum matches the desired value.
Problem Statement
The problem is to find and print all subsets of an array that have a sum equal to a given target value. The input consists of an array of integers and a target sum value. We need to find all possible combinations of elements from the array that add up to the target sum.
For example, let's say we have the set [1, 2, 3, 4, 5] and the target sum is 7. The subsets that add up to 7 are [2, 5] and [3, 4].
Pseudocode Algorithm
Here is the pseudocode algorithm for the program:
subsets(n, inputs, result, size, index, sum)
if index > n or sum > n
return
if sum == n
for i from 0 to index
print result[i]
print new line
else
for i from 0 to size
result[index] = inputs[i]
subsets(n, inputs, result, size, index + 1, sum + inputs[i])
main()
inputs = [1, 2, 3, 4, 5, 6]
size = length of inputs array
n = target sum
result = array of size 'size'
subsets(n, inputs, result, size, 0, 0)
The subsets function takes several parameters: n represents the target sum, inputs is the input array, result is an array used to store the subsets, size is the size of the input array, index keeps track of the current index in the result array, and sum stores the current sum of elements in the result array.
The function first checks if the current index is greater than the size of the array or if the current sum is greater than the target sum. If either condition is true, the function returns.
If the sum is equal to the target sum, the function prints the elements in the result array. Otherwise, it iterates over the elements in the input array and recursively calls the subsets function, incrementing the index and updating the sum by adding the current element. This process generates all possible subsets of the input array.
Code Solution
//C Program
//Print all subsets with given sum
#include <stdio.h>
//This function are print all exist subset of given sum in input array
void subsets(int n ,
int inputs[],
int result[] ,
int size,
int index,
int sum)
{
if(index > n || sum > n) return;
if(sum == n)
{
//When resultant pair are get
for (int i = 0; i < index; ++i)
{
printf("%3d",result[i] );
}
printf("\n");
}
else
{
for (int i = 0; i < size; ++i)
{
//Get result elements
result[index] = inputs[i];
//Recursive call
subsets(n ,inputs,result,size,index+1,sum + inputs[i]);
}
}
}
int main()
{
//array elements
int inputs[] ={1,2,3,4,5,6};
//Get the size of array elements
int size=(sizeof(inputs))/sizeof(inputs[0]);
int n=5; //perfect sum
//Auxiliary space which is store the result
int result[size];
//show all subset
subsets(n,inputs,result,size,0,0);
return 0;
}Output
1 1 1 1 1
1 1 1 2
1 1 2 1
1 1 3
1 2 1 1
1 2 2
1 3 1
1 4
2 1 1 1
2 1 2
2 2 1
2 3
3 1 1
3 2
4 1
5
//C++ Program
//Print all subsets with given sum
#include <iostream>
using namespace std;
class MyArray
{
public:
void subsets(int,int [],int [],int ,int,int);
};
//This function are print all exist subset of given sum in input array
void MyArray :: subsets(int n ,
int inputs[],
int result[] ,
int size,
int index,
int sum)
{
if(index > n || sum > n) return;
if(sum == n)
{
//When resultant pair are get
for (int i = 0; i < index; ++i)
{
cout<<" "<<result[i] ;
}
cout<<("\n");
}
else
{
for (int i = 0; i < size; ++i)
{
//Get result elements
result[index] = inputs[i];
//Recursive call
subsets(n ,inputs,result,size,index+1,sum + inputs[i]);
}
}
}
int main()
{
MyArray obj;
//array elements
int inputs[] ={1,2,3,4,5,6};
//Get the size of array elements
int size=(sizeof(inputs))/sizeof(inputs[0]);
int n=5; //perfect sum
//Auxiliary space which is store the result
int result[size];
//show all subset
obj.subsets(n,inputs,result,size,0,0);
return 0;
}Output
1 1 1 1 1
1 1 1 2
1 1 2 1
1 1 3
1 2 1 1
1 2 2
1 3 1
1 4
2 1 1 1
2 1 2
2 2 1
2 3
3 1 1
3 2
4 1
5
//Java program
//Print all subsets with given sum
public class MyArray
{
//This function are print all exist subset of given sum in input array
public void subsets(int n ,
int []inputs,
int []result,
int size,
int index,
int sum)
{
if(index > n || sum > n) return;
if(sum == n)
{
//When resultant pair are get
for (int i = 0; i < index; ++i)
{
System.out.print(" "+result[i]) ;
}
System.out.println();
}
else
{
for (int i = 0; i < size; ++i)
{
//Get result elements
result[index] = inputs[i];
//Recursive call
subsets(n ,inputs,result,size,index+1,sum + inputs[i]);
}
}
}
public static void main(String[] args)
{
MyArray obj = new MyArray();
//array elements
int []inputs ={1,2,3,4,5,6};
//Get the size of array elements
int size=inputs.length;
int n=5; //perfect sum
//Auxiliary space which is store the result
int []result=new int[size];
//show all subset
obj.subsets(n,inputs,result,size,0,0);
}
}Output
1 1 1 1 1
1 1 1 2
1 1 2 1
1 1 3
1 2 1 1
1 2 2
1 3 1
1 4
2 1 1 1
2 1 2
2 2 1
2 3
3 1 1
3 2
4 1
5
#Python Program
#Print all subsets with given sum
class MyArray:
def subsets(self,
n ,
inputs,
result,
size,
index,
sum):
if(index > n or sum > n) :
return
if(sum == n):
#When resultant pair are get
for x in range(0,index):
print(result[x],end=" ")
print()
else :
for element in inputs:
#Get result elements
result[index] = element
#Recursive call
self.subsets(n, inputs,result,size,index+1,sum + element)
def main():
obj = MyArray()
#list elements
inputs =[1,2,3,4,5,6]
#Get the size of array elements
size=len(inputs)
n=5 #perfect sum
#Auxiliary space which is store the result
result=[0]*size
#show all subset
obj.subsets(n,inputs,result,size,0,0)
if __name__ =="__main__":
main()Output
1 1 1 1 1
1 1 1 2
1 1 2 1
1 1 3
1 2 1 1
1 2 2
1 3 1
1 4
2 1 1 1
2 1 2
2 2 1
2 3
3 1 1
3 2
4 1
5
//C# program
//Print all subsets with given sum
using System;
public class MyArray
{
//This function are print all exist subset of given sum in input array
public void subsets(int n ,
int []inputs,
int []result,
int size,
int index,
int sum)
{
if(index > n || sum > n) return;
if(sum == n)
{
//When resultant pair are get
for (int i = 0; i < index; ++i)
{
Console.Write(" "+result[i]) ;
}
Console.WriteLine();
}
else
{
for (int i = 0; i < size; ++i)
{
//Get result elements
result[index] = inputs[i];
//Recursive call
subsets(n ,inputs,result,size,index+1,sum + inputs[i]);
}
}
}
public static void Main(String[] args)
{
MyArray obj = new MyArray();
//array elements
int []inputs ={1,2,3,4,5,6};
//Get the size of array elements
int size=inputs.Length;
int n=5; //perfect sum
//Auxiliary space which is store the result
int []result=new int[size];
//show all subset
obj.subsets(n,inputs,result,size,0,0);
}
}Output
1 1 1 1 1
1 1 1 2
1 1 2 1
1 1 3
1 2 1 1
1 2 2
1 3 1
1 4
2 1 1 1
2 1 2
2 2 1
2 3
3 1 1
3 2
4 1
5
<?php
//Php program
//Print all subsets with given sum
class MyArray
{
//This function are pr$all exist subset of given sum in input array
function subsets($n,
$inputs,
$result,
$size,
$index,
$sum)
{
if($index > $n || $sum > $n) return;
if($sum == $n)
{
//When resultant pair are get
for ($i = 0; $i < $index; ++$i)
{
echo " ".$result[$i] ;
}
echo ("\n");
}
else
{
for ($i = 0; $i < $size; ++$i)
{
//Get result elements
$result[$index] = $inputs[$i];
//Recursive call
$this->subsets($n ,$inputs,$result,$size,$index+1,$sum + $inputs[$i]);
}
}
}
}
function main()
{
$obj= new MyArray();
$inputs = array(1,2,3,4,5,6);
$size = count($inputs);
$n = 5;
$result = array_fill(0, $size, 0);
//show all subset
$obj->subsets($n,$inputs,$result,$size,0,0);
}
main();
?>Output
1 1 1 1 1
1 1 1 2
1 1 2 1
1 1 3
1 2 1 1
1 2 2
1 3 1
1 4
2 1 1 1
2 1 2
2 2 1
2 3
3 1 1
3 2
4 1
5
//Node Js program
//Print all subsets with given sum
class MyArray {
//This function are print all exist subset of given sum in input array
subsets(n, inputs, result, size, index, sum) {
if (index > n ||
sum > n)
return;
if (sum == n) {
//When resultant pair are get
for (var i = 0; i < index; ++i) {
process.stdout.write(" " + result[i]);
}
process.stdout.write("\n");
} else {
for (var i = 0; i < size; ++i) {
//Get result elements
result[index] = inputs[i];
//Recursive call
this.subsets(n, inputs, result, size, index + 1, sum + inputs[i]);
}
}
}
}
function main(args) {
var obj = new MyArray();
//array elements
var inputs = [1, 2, 3, 4, 5, 6];
//Get the size of array elements
var size = inputs.length;
var n = 5;
//perfect sum
//Auxiliary space which is store the result
var result = Array(size).fill(0);
//show all subset
obj.subsets(n, inputs, result, size, 0, 0);
}
main();
Output
1 1 1 1 1
1 1 1 2
1 1 2 1
1 1 3
1 2 1 1
1 2 2
1 3 1
1 4
2 1 1 1
2 1 2
2 2 1
2 3
3 1 1
3 2
4 1
5# Ruby program
# Print all subsets with given sum
class MyArray
# This function are print all exist subset of given sum in input array
def subsets(n, inputs, result, size, index, sum)
if (index > n ||
sum > n)
return
end
if (sum == n)
# When resultant pair are get
i = 0
while (i < index)
print(" ", result[i])
i += 1
end
print("\n")
else
i = 0
while (i < size)
# Get result elements
result[index] = inputs[i]
self.subsets(n, inputs, result, size, index + 1, sum + inputs[i])
i += 1
end
end
end
end
def main()
obj = MyArray.new()
inputs = [1, 2, 3, 4, 5, 6]
size = inputs.length
n = 5
result = Array.new(n) {0}
obj.subsets(n, inputs, result, size, 0, 0)
end
main()
Output
1 1 1 1 1
1 1 1 2
1 1 2 1
1 1 3
1 2 1 1
1 2 2
1 3 1
1 4
2 1 1 1
2 1 2
2 2 1
2 3
3 1 1
3 2
4 1
5
//Scala program
//Print all subsets with given sum
class MyArray {
//This function are print all exist subset of given sum in input array
def subsets(n: Int, inputs: Array[Int], result: Array[Int], size: Int, index: Int, sum: Int): Unit = {
if (index > n ||
sum > n) {
return;
}
var i: Int = 0;
if (sum == n) {
//When resultant pair are get
i = 0;
while (i < index) {
print(" " + result(i));
i += 1;
}
print("\n");
} else {
i = 0;
while (i < size) {
//Get result elements
result(index) = inputs(i);
subsets(n, inputs, result, size, index + 1, sum + inputs(i));
i += 1;
}
}
}
}
object Main {
def main(args: Array[String]): Unit = {
var obj: MyArray = new MyArray();
var inputs: Array[Int] = Array(1, 2, 3, 4, 5, 6);
var size: Int = inputs.length;
var n: Int = 5;
var result: Array[Int] = Array.fill[Int](size)(0);
obj.subsets(n, inputs, result, size, 0, 0);
}
}
Output
1 1 1 1 1
1 1 1 2
1 1 2 1
1 1 3
1 2 1 1
1 2 2
1 3 1
1 4
2 1 1 1
2 1 2
2 2 1
2 3
3 1 1
3 2
4 1
5//Swift program
//Print all subsets with given sum
class MyArray {
//This function are print all exist subset of given sum in input array
func subsets(_ n: Int, _ inputs: [Int], _ result: inout[Int], _ size: Int, _ index: Int, _ sum: Int) {
if (index > n ||
sum > n) {
return;
}
var i: Int = 0;
if (sum == n) {
//When resultant pair are get
while (i < index) {
print(" ", result[i], terminator: "");
i += 1;
}
print("\n", terminator: "");
} else {
while (i < size) {
//Get result elements
result[index] = inputs[i];
self.subsets(n, inputs, &result, size, index + 1, sum + inputs[i]);
i += 1;
}
}
}
}
func main() {
let obj: MyArray = MyArray();
let inputs: [Int] = [1, 2, 3, 4, 5, 6];
let size: Int = inputs.count;
let n: Int = 5;
var result: [Int] = Array(repeating: 0, count: size);
obj.subsets(n, inputs, &result, size, 0, 0);
}
main();
Output
1 1 1 1 1
1 1 1 2
1 1 2 1
1 1 3
1 2 1 1
1 2 2
1 3 1
1 4
2 1 1 1
2 1 2
2 2 1
2 3
3 1 1
3 2
4 1
5Result Explanation
The output of the program corresponds to all the subsets of the input array that add up to the target sum. Each line represents a subset, and the numbers in the line represent the elements of the subset.
For example, in the given output:
1 1 1 1 1
1 1 1 2
1 1 2 1
1 1 3
1 2 1 1
1 2 2
1 3 1
1 4
2 1 1 1
2 1 2
2 2 1
2 3
3 1 1
3 2
4 1
5
The first line represents a subset containing five elements with a value of 1 each. The second line represents a subset with four elements, three of which have a value of 1 and one with a value of 2. The subsets continue to be printed, showing all possible combinations that add up to the target sum.
Time Complexity
The time complexity of the program depends on the number of subsets that satisfy the given sum condition. In the worst case, where all possible subsets are valid, the time complexity is exponential, O(2^N), where N is the size of the input array. This is because each element has two choices: either to be included in a subset or not.
It's important to note that the program may terminate early when it encounters subsets that exceed the target sum, which can improve the overall execution time.
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