Skip to main content

Subset sum problem using dynamic programming

Here given code implementation process.

/*
    Java program for
    Subset sum problem using dynamic programming
*/
public class SubSets
{
    public void checkSubsetSum(int data[], int n, int sum)
    {
        boolean result = true;
        if (sum < 0)
        {
            // Because set include positive values
            result = false;
        }
        else
        {
            // Assume of, given data contains positive integers
            boolean subset[][] = new boolean[sum + 1][n + 1];
            // Set value of first row in in subset
            for (int i = 0; i <= n && result; ++i)
            {
                if (i < n && data[i] < 0)
                {
                    // Invalid inputs
                    // It will work on only positive values
                    result = false;
                }
                // When subset sum is zero then result is true
                subset[0][i] = true;
            }
            // Set value of first column in in subset
            for (int i = 1; i <= sum && result; ++i)
            {
                // When subset sum is not zero then result is false
                subset[i][0] = false;
            }
            for (int i = 1; i <= sum && result; ++i)
            {
                for (int j = 1; j <= n; ++j)
                {
                    // Get a previous element in row
                    subset[i][j] = subset[i][j - 1];
                    if (i >= data[j - 1])
                    {
                        // Update sub sets value
                        subset[i][j] = subset[i][j] || 
                                   subset[i - data[j - 1]][j - 1];
                    }
                }
            }
            if (subset[sum][n] && result)
            {
                result = true;
            }
            else
            {
                result = false;
            }
        }
        if (result)
        {
            System.out.print("SubSet sum " + sum + " are found\n");
        }
        else
        {
            System.out.print("SubSet sum " + sum + " are not found\n");
        }
    }
    public static void main(String[] args)
    {
        SubSets task = new SubSets();
        // Data set which containing positive inputs
        int[] data = {
            1 , 12 , 9 , 3 , 7 , 4 , 10
        };

        int n = data.length;
        // Test A
        // Sum = 18
        // 1 + 7 + 10 = 18
        task.checkSubsetSum(data, n, 18);
        // Test B
        // Sum = 40
        task.checkSubsetSum(data, n, 40);
      
    }
}

Output

SubSet sum 18 are found
SubSet sum 40 are not found
// Include header file
#include <iostream>

using namespace std;
/*
    C++ program for
    Subset sum problem using dynamic programming
*/
class SubSets
{
  public: void checkSubsetSum(int data[], int n, int sum)
  {
    bool result = true;
    if (sum < 0)
    {
      // Because set include positive values
      result = false;
    }
    else
    {
      // Assume of, given data contains positive integers
      bool subset[sum + 1][n + 1];
      // Set value of first row in in subset
      for (int i = 0; i <= n && result; ++i)
      {
        if (i < n && data[i] < 0)
        {
          // Invalid inputs
          // It will work on only positive values
          result = false;
        }
        // When subset sum is zero then result is true
        subset[0][i] = true;
      }
      // Set value of first column in in subset
      for (int i = 1; i <= sum && result; ++i)
      {
        // When subset sum is not zero then result is false
        subset[i][0] = false;
      }
      for (int i = 1; i <= sum && result; ++i)
      {
        for (int j = 1; j <= n; ++j)
        {
          // Get a previous element in row
          subset[i][j] = subset[i][j - 1];
          if (i >= data[j - 1])
          {
            // Update sub sets value
            subset[i][j] = subset[i][j] || 
                          subset[i - data[j - 1]][j - 1];
          }
        }
      }
      if (subset[sum][n] && result)
      {
        result = true;
      }
      else
      {
        result = false;
      }
    }
    if (result)
    {
      cout << "SubSet sum " << sum << " are found\n";
    }
    else
    {
      cout << "SubSet sum " << sum << " are not found\n";
    }
  }
};
int main()
{
  SubSets *task = new SubSets();
  // Data set which containing positive inputs
  int data[] = {
    1 , 12 , 9 , 3 , 7 , 4 , 10
  };
  int n = sizeof(data) / sizeof(data[0]);
  // Test A
  // Sum = 18
  // 1 + 7 + 10 = 18
  task->checkSubsetSum(data, n, 18);
  // Test B
  // Sum = 40
  task->checkSubsetSum(data, n, 40);
  return 0;
}

Output

SubSet sum 18 are found
SubSet sum 40 are not found
// Include namespace system
using System;
/*
    Csharp program for
    Subset sum problem using dynamic programming
*/
public class SubSets
{
  public void checkSubsetSum(int[] data, int n, int sum)
  {
    Boolean result = true;
    if (sum < 0)
    {
      // Because set include positive values
      result = false;
    }
    else
    {
      // Assume of, given data contains positive integers
      Boolean[,] subset = new Boolean[sum + 1,n + 1];
      // Set value of first row in in subset
      for (int i = 0; i <= n && result; ++i)
      {
        if (i < n && data[i] < 0)
        {
          // Invalid inputs
          // It will work on only positive values
          result = false;
        }
        // When subset sum is zero then result is true
        subset[0,i] = true;
      }
      // Set value of first column in in subset
      for (int i = 1; i <= sum && result; ++i)
      {
        // When subset sum is not zero then result is false
        subset[i,0] = false;
      }
      for (int i = 1; i <= sum && result; ++i)
      {
        for (int j = 1; j <= n; ++j)
        {
          // Get a previous element in row
          subset[i,j] = subset[i,j - 1];
          if (i >= data[j - 1])
          {
            // Update sub sets value
            subset[i,j] = subset[i,j] || 
                          subset[i - data[j - 1],j - 1];
          }
        }
      }
      if (subset[sum,n] && result)
      {
        result = true;
      }
      else
      {
        result = false;
      }
    }
    if (result)
    {
      Console.Write("SubSet sum " + sum + " are found\n");
    }
    else
    {
      Console.Write("SubSet sum " + sum + " are not found\n");
    }
  }
  public static void Main(String[] args)
  {
    SubSets task = new SubSets();
    // Data set which containing positive inputs
    int[] data = {
      1 , 12 , 9 , 3 , 7 , 4 , 10
    };
    int n = data.Length;
    // Test A
    // Sum = 18
    // 1 + 7 + 10 = 18
    task.checkSubsetSum(data, n, 18);
    // Test B
    // Sum = 40
    task.checkSubsetSum(data, n, 40);
  }
}

Output

SubSet sum 18 are found
SubSet sum 40 are not found
package main
import "fmt"
/*
    Go program for
    Subset sum problem using dynamic programming
*/

func checkSubsetSum(data []int, n int, sum int) {
  var result bool = true
  if sum < 0 {
    // Because set include positive values
    result = false
  } else {
    // Assume of, given data contains positive integers
    var subset = make([][]bool,sum+1)

    for i := range subset {
      subset[i] = make([]bool, n+1)
    }
    // Set value of first row in in subset
    for i := 0 ; i <= n && result ; i++ {
      if i < n && data[i] < 0 {
        // Invalid inputs
        // It will work on only positive values
        result = false
      }
      // When subset sum is zero then result is true
      subset[0][i] = true
    }
    // Set value of first column in in subset
    for i := 1 ; i <= sum && result ; i++ {
      // When subset sum is not zero then result is false
      subset[i][0] = false
    }
    for i := 1 ; i <= sum && result ; i++ {
      for j := 1 ; j <= n ; j++ {
        // Get a previous element in row
        subset[i][j] = subset[i][j - 1]
        if i >= data[j - 1] {
          // Update sub sets value
          subset[i][j] = subset[i][j] || subset[i - data[j - 1]][j - 1]
        }
      }
    }
    if subset[sum][n] && result {
      result = true
    } else {
      result = false
    }
  }
  if result {
    fmt.Print("SubSet sum ", sum, " are found\n")
  } else {
    fmt.Print("SubSet sum ", sum, " are not found\n")
  }
}
func main() {

  // Data set which containing positive inputs
  var data = [] int {1 , 12 , 9 , 3 , 7 , 4 , 10}
  var n int = len(data)
  // Test A
  // Sum = 18
  // 1 + 7 + 10 = 18
  checkSubsetSum(data, n, 18)
  // Test B
  // Sum = 40
  checkSubsetSum(data, n, 40)
}

Output

SubSet sum 18 are found
SubSet sum 40 are not found
<?php
/*
    Php program for
    Subset sum problem using dynamic programming
*/
class SubSets
{
  public  function checkSubsetSum($data, $n, $sum)
  {
    $result = true;
    if ($sum < 0)
    {
      // Because set include positive values
      $result = false;
    }
    else
    {
      // Assume of, given data contains positive integers
      $subset = array_fill(0, $sum + 1, array_fill(0, $n + 1, false));
      // Set value of first row in in subset
      for ($i = 0; $i <= $n && $result; ++$i)
      {
        if ($i < $n && $data[$i] < 0)
        {
          // Invalid inputs
          // It will work on only positive values
          $result = false;
        }
        // When subset sum is zero then result is true
        $subset[0][$i] = true;
      }
    
      for ($i = 1; $i <= $sum && $result; ++$i)
      {
        for ($j = 1; $j <= $n; ++$j)
        {
          // Get a previous element in row
          $subset[$i][$j] = $subset[$i][$j - 1];
          if ($i >= $data[$j - 1])
          {
            // Update sub sets value
            $subset[$i][$j] = $subset[$i][$j] || 
                          $subset[$i - $data[$j - 1]][$j - 1];
          }
        }
      }
      if ($subset[$sum][$n] && $result)
      {
        $result = true;
      }
      else
      {
        $result = false;
      }
    }
    if ($result)
    {
      echo("SubSet sum ".$sum." are found\n");
    }
    else
    {
      echo("SubSet sum ".$sum." are not found\n");
    }
  }
}

function main()
{
  $task = new SubSets();
  // Data set which containing positive inputs
  $data = array(1, 12, 9, 3, 7, 4, 10);
  $n = count($data);
  // Test A
  // Sum = 18
  // 1 + 7 + 10 = 18
  $task->checkSubsetSum($data, $n, 18);
  // Test B
  // Sum = 40
  $task->checkSubsetSum($data, $n, 40);
}
main();

Output

SubSet sum 18 are found
SubSet sum 40 are not found
/*
    Node JS program for
    Subset sum problem using dynamic programming
*/
class SubSets
{
  checkSubsetSum(data, n, sum)
  {
    var result = true;
    if (sum < 0)
    {
      // Because set include positive values
      result = false;
    }
    else
    {
      // Assume of, given data contains positive integers
      var subset = Array(sum + 1).fill(false).map(
              () => new Array(n + 1).fill(false));
      // Set value of first row in in subset
      for (var i = 0; i <= n && result; ++i)
      {
        if (i < n && data[i] < 0)
        {
          // Invalid inputs
          // It will work on only positive values
          result = false;
        }
        // When subset sum is zero then result is true
        subset[0][i] = true;
      }
      // Set value of first column in in subset
      for (var i = 1; i <= sum && result; ++i)
      {
        // When subset sum is not zero then result is false
        subset[i][0] = false;
      }
      for (var i = 1; i <= sum && result; ++i)
      {
        for (var j = 1; j <= n; ++j)
        {
          // Get a previous element in row
          subset[i][j] = subset[i][j - 1];
          if (i >= data[j - 1])
          {
            // Update sub sets value
            subset[i][j] = subset[i][j] || 
                          subset[i - data[j - 1]][j - 1];
          }
        }
      }
      if (subset[sum][n] && result)
      {
        result = true;
      }
      else
      {
        result = false;
      }
    }
    if (result)
    {
      process.stdout.write("SubSet sum " + sum + " are found\n");
    }
    else
    {
      process.stdout.write("SubSet sum " + sum + " are not found\n");
    }
  }
}

function main()
{
  var task = new SubSets();
  // Data set which containing positive inputs
  var data = [1, 12, 9, 3, 7, 4, 10];
  var n = data.length;
  // Test A
  // Sum = 18
  // 1 + 7 + 10 = 18
  task.checkSubsetSum(data, n, 18);
  // Test B
  // Sum = 40
  task.checkSubsetSum(data, n, 40);
}
main();

Output

SubSet sum 18 are found
SubSet sum 40 are not found
#    Python 3 program for
#    Subset sum problem using dynamic programming
class SubSets :
  def checkSubsetSum(self, data, n, sum) :
    result = True
    if (sum < 0) :
      #  Because set include positive values
      result = False
    else :
      #  Assume of, given data contains positive integers
      subset = [[False] * (n + 1) for _ in range(sum + 1) ]
      i = 0
      #  Set value of first row in in subset
      while (i <= n and result) :
        if (i < n and data[i] < 0) :
          #  Invalid inputs
          #  It will work on only positive values
          result = False
        
        #  When subset sum is zero then result is true
        subset[0][i] = True
        i += 1
      
      i = 1
      #  Set value of first column in in subset
      while (i <= sum and result) :
        #  When subset sum is not zero then result is false
        subset[i][0] = False
        i += 1
      
      i = 1
      while (i <= sum and result) :
        j = 1
        while (j <= n) :
          #  Get a previous element in row
          subset[i][j] = subset[i][j - 1]
          if (i >= data[j - 1]) :
            #  Update sub sets value
            subset[i][j] = subset[i][j] or subset[i - data[j - 1]][j - 1]
          
          j += 1
        
        i += 1
      
      if (subset[sum][n] and result) :
        result = True
      else :
        result = False
      
    
    if (result) :
      print("SubSet sum", sum ,"are found")
    else :
      print("SubSet sum", sum ,"are not found")
    
  

def main() :
  task = SubSets()
  #  Data set which containing positive inputs
  data = [1, 12, 9, 3, 7, 4, 10]
  n = len(data)
  #  Test A
  #  Sum = 18
  #  1 + 7 + 10 = 18
  task.checkSubsetSum(data, n, 18)
  #  Test B
  #  Sum = 40
  task.checkSubsetSum(data, n, 40)

if __name__ == "__main__": main()

Output

SubSet sum 18 are found
SubSet sum 40 are not found
#    Ruby program for
#    Subset sum problem using dynamic programming
class SubSets 
  def checkSubsetSum(data, n, sum) 
    result = true
    if (sum < 0) 
      #  Because set include positive values
      result = false
    else
 
      #  Assume of, given data contains positive integers
      subset = Array.new(sum + 1) {Array.new(n + 1) {false}}
      i = 0
      #  Set value of first row in in subset
      while (i <= n && result) 
        if (i < n && data[i] < 0) 
          #  Invalid inputs
          #  It will work on only positive values
          result = false
        end

        #  When subset sum is zero then result is true
        subset[0][i] = true
        i += 1
      end

      i = 1
      #  Set value of first column in in subset
      while (i <= sum && result) 
        #  When subset sum is not zero then result is false
        subset[i][0] = false
        i += 1
      end

      i = 1
      while (i <= sum && result) 
        j = 1
        while (j <= n) 
          #  Get a previous element in row
          subset[i][j] = subset[i][j - 1]
          if (i >= data[j - 1]) 
            #  Update sub sets value
            subset[i][j] = subset[i][j] || 
                          subset[i - data[j - 1]][j - 1]
          end

          j += 1
        end

        i += 1
      end

      if (subset[sum][n] && result) 
        result = true
      else
 
        result = false
      end

    end

    if (result) 
      print("SubSet sum ", sum ," are found\n")
    else
 
      print("SubSet sum ", sum ," are not found\n")
    end

  end

end

def main() 
  task = SubSets.new()
  #  Data set which containing positive inputs
  data = [1, 12, 9, 3, 7, 4, 10]
  n = data.length
  #  Test A
  #  Sum = 18
  #  1 + 7 + 10 = 18
  task.checkSubsetSum(data, n, 18)
  #  Test B
  #  Sum = 40
  task.checkSubsetSum(data, n, 40)
end

main()

Output

SubSet sum 18 are found
SubSet sum 40 are not found

/*
    Scala program for
    Subset sum problem using dynamic programming
*/
class SubSets()
{
  def checkSubsetSum(data: Array[Int], n: Int, sum: Int): Unit = {
    var result: Boolean = true;
    if (sum < 0)
    {
      // Because set include positive values
      result = false;
    }
    else
    {
      // Assume of, given data contains positive integers
      var subset: Array[Array[Boolean]] = 
              Array.fill[Boolean](sum + 1, n + 1)(false);
      var i: Int = 0;
      // Set value of first row in in subset
      while (i <= n && result)
      {
        if (i < n && data(i) < 0)
        {
          // Invalid inputs
          // It will work on only positive values
          result = false;
        }
        // When subset sum is zero then result is true
        subset(0)(i) = true;
        i += 1;
      }
      i = 1;
      // Set value of first column in in subset
      while (i <= sum && result)
      {
        // When subset sum is not zero then result is false
        subset(i)(0) = false;
        i += 1;
      }
      i = 1;
      while (i <= sum && result)
      {
        var j: Int = 1;
        while (j <= n)
        {
          // Get a previous element in row
          subset(i)(j) = subset(i)(j - 1);
          if (i >= data(j - 1))
          {
            // Update sub sets value
            subset(i)(j) = subset(i)(j) || 
                          subset(i - data(j - 1))(j - 1);
          }
          j += 1;
        }
        i += 1;
      }
      if (subset(sum)(n) && result)
      {
        result = true;
      }
      else
      {
        result = false;
      }
    }
    if (result)
    {
      print("SubSet sum " + sum + " are found\n");
    }
    else
    {
      print("SubSet sum " + sum + " are not found\n");
    }
  }
}
object Main
{
  def main(args: Array[String]): Unit = {
    var task: SubSets = new SubSets();
    // Data set which containing positive inputs
    var data: Array[Int] = Array(1, 12, 9, 3, 7, 4, 10);
    var n: Int = data.length;
    // Test A
    // Sum = 18
    // 1 + 7 + 10 = 18
    task.checkSubsetSum(data, n, 18);
    // Test B
    // Sum = 40
    task.checkSubsetSum(data, n, 40);
  }
}

Output

SubSet sum 18 are found
SubSet sum 40 are not found
import Foundation;
/*
    Swift 4 program for
    Subset sum problem using dynamic programming
*/
class SubSets
{
  func checkSubsetSum(_ data: [Int], _ n: Int, _ sum: Int)
  {
    var result: Bool = true;
    if (sum < 0)
    {
      // Because set include positive values
      result = false;
    }
    else
    {
      // Assume of, given data contains positive integers
      var subset: [
        [Bool]
      ] = Array(repeating: Array(repeating: false, count: n + 1), 
              count: sum + 1);
      var i: Int = 0;
      // Set value of first row in in subset
      while (i <= n && result)
      {
        if (i < n && data[i] < 0)
        {
          // Invalid inputs
          // It will work on only positive values
          result = false;
        }
        // When subset sum is zero then result is true
        subset[0][i] = true;
        i += 1;
      }
      i = 1;
      // Set value of first column in in subset
      while (i <= sum && result)
      {
        // When subset sum is not zero then result is false
        subset[i][0] = false;
        i += 1;
      }
      i = 1;
      while (i <= sum && result)
      {
        var j: Int = 1;
        while (j <= n)
        {
          // Get a previous element in row
          subset[i][j] = subset[i][j - 1];
          if (i >= data[j - 1])
          {
            // Update sub sets value
            subset[i][j] = subset[i][j] || 
                          subset[i - data[j - 1]][j - 1];
          }
          j += 1;
        }
        i += 1;
      }
      if (subset[sum][n] && result)
      {
        result = true;
      }
      else
      {
        result = false;
      }
    }
    if (result)
    {
      print("SubSet sum", sum ,"are found");
    }
    else
    {
      print("SubSet sum", sum ,"are not found");
    }
  }
}
func main()
{
  let task: SubSets = SubSets();
  // Data set which containing positive inputs
  let data: [Int] = [1, 12, 9, 3, 7, 4, 10];
  let n: Int = data.count;
  // Test A
  // Sum = 18
  // 1 + 7 + 10 = 18
  task.checkSubsetSum(data, n, 18);
  // Test B
  // Sum = 40
  task.checkSubsetSum(data, n, 40);
}
main();

Output

SubSet sum 18 are found
SubSet sum 40 are not found
/*
    Kotlin program for
    Subset sum problem using dynamic programming
*/
class SubSets
{
  fun checkSubsetSum(data: Array < Int > , n: Int, sum: Int): Unit
  {
    var result: Boolean = true;
    if (sum < 0)
    {
      // Because set include positive values
      result = false;
    }
    else
    {
      // Assume of, given data contains positive integers
      val subset: Array < Array < Boolean >> = Array(sum + 1)
      {
        Array(n + 1)
        {
          false
        }
      };
      var i: Int = 0;
      // Set value of first row in in subset
      while (i <= n && result)
      {
        if (i < n && data[i] < 0)
        {
          // Invalid inputs
          // It will work on only positive values
          result = false;
        }
        // When subset sum is zero then result is true
        subset[0][i] = true;
        i += 1;
      }
      i = 1;
      // Set value of first column in in subset
      while (i <= sum && result)
      {
        // When subset sum is not zero then result is false
        subset[i][0] = false;
        i += 1;
      }
      i = 1;
      while (i <= sum && result)
      {
        var j: Int = 1;
        while (j <= n)
        {
          // Get a previous element in row
          subset[i][j] = subset[i][j - 1];
          if (i >= data[j - 1])
          {
            // Update sub sets value
            subset[i][j] = subset[i][j] || subset[i - data[j - 1]][j - 1];
          }
          j += 1;
        }
        i += 1;
      }
      if (subset[sum][n] && result)
      {
        result = true;
      }
      else
      {
        result = false;
      }
    }
    if (result)
    {
      print("SubSet sum " + sum + " are found\n");
    }
    else
    {
      print("SubSet sum " + sum + " are not found\n");
    }
  }
}
fun main(args: Array < String > ): Unit
{
  val task: SubSets = SubSets();
  // Data set which containing positive inputs
  val data: Array < Int > = arrayOf(1, 12, 9, 3, 7, 4, 10);
  val n: Int = data.count();
  // Test A
  // Sum = 18
  // 1 + 7 + 10 = 18
  task.checkSubsetSum(data, n, 18);
  // Test B
  // Sum = 40
  task.checkSubsetSum(data, n, 40);
}

Output

SubSet sum 18 are found
SubSet sum 40 are not found
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