Package org.drip.graph.subarray

Class SubsetSum

java.lang.Object
org.drip.graph.subarray.SubsetSum
Direct Known Subclasses:
HorowitzSahni, PolynomialTimeApproximate, PseudoPolynomialDP
public abstract class SubsetSum
extends java.lang.Object
SubsetSum finds out is there is a non-empty Subset in the specified Array that adds up to the Specified Target. The References are:

  • Bringmann, K. (2017): A near-linear Pseudo-polynomial Time Algorithm for Subset Sums Proceedings of the 28th Annual ACM SIAM Symposium on Discrete Algorithms 1073-1084
  • Horowitz, E., and S. Sahni (1974): Computing Partitions with Applications to the Knapsack Problem Journal of the ACM 21 (2) 277-292
  • Kleinberg, J., and E. Tardos (2022): Algorithm Design 2nd Edition Pearson
  • Koiliaris, K., and C. Xu (2016): A Faster Pseudo-polynomial Time Algorithm for Subset Sum https://arxiv.org/abs/1507.02318 arXiV
  • Wikipedia (2020): Subset Sum Problem https://en.wikipedia.org/wiki/Subset_sum_problem




Author:
Lakshmi Krishnamurthy

  • Method Summary

    Modifier and Type Method Description
    int[] numberArray()
    Retrieve the Number Array
    int target()
    Retrieve the Target
    abstract boolean targetSumExists()
    Indicate if the Target Sum Match exists

    Methods inherited from class java.lang.Object

    equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Method Details

    • numberArray

      public int[] numberArray()
      Retrieve the Number Array
      Returns:
      The Number Array

    • target

      public int target()
      Retrieve the Target
      Returns:
      The Target

    • targetSumExists

      public abstract boolean targetSumExists()
      Indicate if the Target Sum Match exists
      Returns:
      TRUE - The Target Sum Match exists