The optimization version is NP-hard, but can be solved efficiently in practice.
Not every multiset of positive integers has a partition into two subsets with equal sum.
[6] An instance of SubsetSum consists of a set S of positive integers and a target sum T; the goal is to decide if there is a subset of S with sum exactly T. Given such an instance, construct an instance of Partition in which the input set contains the original set plus two elements: z1 and z2, with z1 = sum(S) and z2 = 2T.
Since the problem is NP-hard, such algorithms might take exponential time in general, but may be practically usable in certain cases.
Algorithms developed for multiway number partitioning include: Algorithms developed for subset sum include: Sets with only one, or no partitions tend to be hardest (or most expensive) to solve compared to their input sizes.
When the values are small compared to the size of the set, perfect partitions are more likely.
This was originally argued based on empirical evidence by Gent and Walsh,[10] then using methods from statistical physics by Mertens,[11][12] and later proved by Borgs, Chayes, and Pittel.
[13] A related problem, somewhat similar to the Birthday paradox, is that of determining the size of the input set so that we have a probability of one half that there is a solution, under the assumption that each element in the set is randomly selected with uniform distribution between 1 and some given value.
[14] Kovalyov and Pesch[15] discuss a generic approach to proving NP-hardness of partition-type problems.
If a coalition wants to ensure that C is elected, they should partition their votes among A and B so as to maximize the smallest number of vetoes each of them gets.