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
• Cpp
• Java
• Python
• C#
• Php
• Node Js
• Ruby
• Scala
• Swift 4

//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;
}

  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;
}

  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);
  }
}

  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()

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);
  }
}

  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();
?>

  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();

 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()

 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);
  }
}

 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();

  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

Result 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.