The Sum Composition Problem
share
In this paper, we study the "sum composition problem" between two lists A and B of positive integers. We start by saying that B is "sum composition" of A when there exists an ordered m-partition [A_1,...,A_m] of A where m is the length of B and the sum of each part A_k is equal to the corresponding part of B. Then, we consider the following two problems: i) the "exhaustive problem", consisting in the generation of all partitions of A for which B is sum composition of A, and ii) the "existential problem", consisting in the verification of the existence of a partition of A for which B is sum composition of A. Starting from some general properties of the sum compositions, we present a first algorithm solving the exhaustive problem and then a second algorithm solving the existential problem. We also provide proofs of correctness and experimental analysis for assessing the quality of the proposed solutions along with a comparison with related works.
READ FULL TEXT