O problema da partição consiste em dividir um conjunto de números em dois grupos, de forma a que somem exatamente o mesmo valor.

Suponhamos a seguinte instância: 5;4;3;2;2. Os valores estão por ordem decrescente, existindo o número 2 repetido. Estes números podem ser colocados em dois grupos 5+3 = 4+2+2.

Considerando o estado vazio como sendo todos os números ainda por colocar, os sucessores de um determinado estado pode consistir na colocação do número mais alto num dos dois grupos. A ramificação é portanto binária, e a profundidade máxima igual à quantidade de números. Poder-se-ia optar por um conjunto de sucessores que consistia em colocar qualquer número num dos grupos, mas assim ter-se-ia uma ramificação muito superior, e é indiferente a ordem pela qual os números são colocados nos grupos.

A representação do estado é autoexplicativa.

Ficheiro de Excel, passo a passo:

A solução foi encontrada com 27 gerações e 25 expansões. No entanto há vários estados que já se saberia não poderem levar a uma divisão válida, mas continuaram a ser explorados. Por exemplo o estado 5, embora num dos grupos já some 9, excedendo portanto o limite de 8, mesmo assim expande-se logo na 3ª expansão este estado, desperdiçando tempo já que não leva a lado nenhum. Para que o algoritmo não incorra nesse tipo de desperdícios, o conjunto de sucessores tem de ser redefinido, não gerando estados em que um dos grupos já ultrapassa metade da soma de todos os números.