Posted on by Kalkicode
Code Dynamic Programming

Subset sum problem using dynamic programming

The subset sum problem is a classic algorithmic problem in computer science and mathematics. Given a set of positive integers and a target sum, the problem is to determine whether there exists a subset of the given set whose elements sum up to the target sum.

This article presents an implementation of the subset sum problem using dynamic programming in Java. Dynamic programming is a technique that solves complex problems by breaking them down into overlapping subproblems and solving them in a bottom-up manner.

Problem Statement:

We are given a set of positive integers and a target sum. We need to determine whether there exists a subset of the given set whose elements sum up to the target sum.

Pseudocode Algorithm:

1. Create a boolean array "subset" of size (sum + 1) x (n + 1), where sum is the target sum and n is the number of elements in the given set.
2. Initialize the first row of the subset array with "true" values, as the sum 0 can be achieved by selecting an empty subset.
3. Initialize the first column of the subset array with "false" values, except for subset[0][0] which is "true."
4. Iterate through the elements of the given set and for each element:
   - Update the subset array as follows:
     - If the current element is greater than the current sum value (i.e., data[j - 1] > i), copy the value from the previous element in the same row.
     - If the current element is less than or equal to the current sum value, update the value as the logical OR of two conditions:
       - The value from the previous element in the same row (subset[i][j - 1]).
       - The value at the corresponding position in the subset array for the reduced sum (subset[i - data[j - 1]][j - 1]).
5. The result will be stored in subset[sum][n]. If it is true, the subset sum is found; otherwise, it is not found.
6. Output the result accordingly.

Code Solution

/*
    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

Explanation:

The given Java code implements the subset sum problem using dynamic programming. It begins by checking the validity of the input sum value. If the sum is less than 0, it is considered invalid, as the set contains only positive integers.

Next, it creates a 2D boolean array called "subset" to store the results of subproblems. The row represents the sum values from 0 to the target sum, and the column represents the elements of the given set.

The code initializes the first row of the subset array to "true" because an empty subset can achieve a sum of 0. It initializes the first column to "false" except for subset[0][0], which remains "true" since a sum of 0 can be achieved by selecting an empty subset.

Using nested loops, the code iterates through the remaining elements of the set and updates the subset array based on the conditions described in the pseudocode algorithm.

Finally, the code checks the value at subset[sum][n] to determine whether a subset sum with the target value is found. The result is then printed accordingly.

Resultant Output Explanation:

The code includes two test cases:

Test A:

The target sum is 18, and the set contains the following elements: [1, 12, 9, 3, 7, 4, 10].

The program determines that a subset sum of 18 is found, and it outputs "SubSet sum 18 are found". This means that the elements [1, 7, 10] can be selected from the set to achieve the target sum.

Test B:

The target sum is 40, and the set remains the same.

The program determines that a subset sum of 40 is not found, and it outputs "SubSet sum 40 are not found". This means that there is no subset of the given set that sums up to 40.

Time Complexity:

The time complexity of the implemented algorithm is O(sum * n), where sum is the target sum and n is the number of elements in the set. The algorithm uses a nested loop structure to iterate through the subset array, which has dimensions (sum + 1) x (n + 1).

Finally:

In this article, we discussed the subset sum problem and its implementation using dynamic programming. We provided a detailed explanation of the algorithm, including pseudocode and the resultant output explanation. Dynamic programming offers an efficient solution to this problem, making it possible to solve larger instances of the subset sum problem in a reasonable amount of time.

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