Skip to main content

Print all subsets with given sum

Here given code implementation process.

//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
  5
Last updated on by Kalkicode




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