HorowitzSahni

java.lang.Object

org.drip.graph.subarray.SubsetSum

org.drip.graph.subarray.HorowitzSahni

public class HorowitzSahni
extends SubsetSum

HorowitzSahni implements the Sub-set Sum Check using the Horowitz-Sahni Scheme. The References are:

Bringmann, K. (2017): A near-linear Pseudo-polynomial Time Algorithm for Subset Sums Proceedings of the 28^th 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 2^nd 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

Module = Computational Core Module
Library = Graph Algorithm Library
Project = Graph Optimization and Tree Construction Algorithms
Package = Sub-set Sum, k-Sum, and Maximum Sub-array Problems

Author:: Lakshmi Krishnamurthy

Constructor Summary

Constructors

Constructor Description

HorowitzSahni(int[] numberArray, int target)
HorowitzSahni Constructor
Method Summary

Modifier and Type Method Description

boolean targetSumExists()
Indicate if the Target Sum Match exists

Methods inherited from class org.drip.graph.subarray.SubsetSum
numberArray, target

Methods inherited from class java.lang.Object
equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details
- HorowitzSahni
  
  public HorowitzSahni(int[] numberArray, int target) throws java.lang.Exception
  
  HorowitzSahni Constructor
  
  Parameters:
  
  numberArray - The Input Number Array
  
  target - The Sum Target
  
  Throws:
  
  java.lang.Exception - Thrown if the Inputs are Invalid
Method Details
- targetSumExists
  
  public boolean targetSumExists()
  
  Description copied from class: SubsetSum
  
  Indicate if the Target Sum Match exists
  
  Specified by:
  
  targetSumExists in class SubsetSum
  
  Returns:
  
  TRUE - The Target Sum Match exists