Partition Equal Subset Sum

Comece pelo total. Se ele for ímpar, não existe divisão, porque a soma de dois números inteiros iguais é sempre par. Caso contrário, cada grupo deve somar exatamente target = total / 2. Depois que você encontrar valores que somem target, os valores que não escolheu formam a outra metade por conta própria. Portanto, basta responder a uma pergunta: existe algum subconjunto que some target?

Percorra os valores em ordem e faça uma escolha para cada um: coloque-o no primeiro grupo ou deixe-o para o segundo. Uma função auxiliar reach(i, remaining) responde se os valores a partir do índice i conseguem somar remaining. Ela retorna true quando remaining chega a 0, false quando não há mais valores ou quando o valor fica abaixo de 0 e, caso contrário, tenta as duas opções para nums[i].

Cada subconjunto corresponde a um caminho de escolhas, então a busca não pode deixar passar nenhuma divisão, e a resposta está correta. Ela é lenta porque há 2^n caminhos, e uma entrada sem divisão faz com que ela tente quase todos eles. Considere 199 cópias de 100 e uma de 98: o total é 19998, o alvo 9999 nunca é atingido, e a busca tenta todas as maneiras de escolher no máximo 99 dos valores 100, cerca de 4 × 10^59 caminhos. Até mesmo 40 valores resultam em 2^40, cerca de 10^12 caminhos.

A recursão faz a mesma pergunta várias vezes. reach(i, remaining) depende apenas de dois números: i, de 0 a n, e remaining, de 0 a target. Isso resulta em, no máximo, (n+1) × (target+1) perguntas diferentes, cerca de 201 × 10001 ≈ 2 × 10^6 nos limites, poucas o suficiente para responder a cada uma delas uma única vez.

Construa as respostas em uma tabela, avançando. can[i][s] indica se alguns dos primeiros i valores somam s. Sem valores, apenas a soma 0 é possível, então a linha 0 é falsa, exceto can[0][0]. O valor num = nums[i-1] oferece duas maneiras de chegar a s: deixar num de fora, então os valores anteriores já somam s, ou incluí-lo, então os valores anteriores somam s-num. Essa é toda a regra: can[i][s] = can[i-1][s] or can[i-1][s-num], em que a segunda parte só conta quando s ≥ num. Cada linha lê apenas a linha acima, então cada valor é usado no máximo uma vez.

Em [6, 1, 4, 9, 2] com alvo 11, as somas alcançáveis aumentam de {0} para {0, 6}, depois para {0, 1, 6, 7} e, então, para {0, 1, 4, 5, 6, 7, 10, 11}. A soma 11 aparece após o 4 (6 + 1 + 4), e as linhas posteriores a mantêm. A resposta é can[n][target]. Cada célula exige trabalho constante, então tanto o tempo quanto a memória são O(n × target).

Cada linha da tabela lê apenas a linha acima dela, então uma única linha basta se você a atualizar no próprio lugar: reach[s] indica se alguns dos valores vistos até agora somam s. O perigo está na ordem das atualizações. Se você percorrer s em ordem crescente, reach[s-num] talvez já tenha sido ativado pelo mesmo num. Com [3, 9] e alvo 6, o 3 marca reach[3] e depois lê esse valor para marcar reach[6], como se você tivesse dois 3s, e a resposta será verdadeira para uma divisão que não existe.

Percorra s em ordem decrescente, de target até num. Assim, s-num é um índice menor que esse valor ainda não alterou, então reach[s-num] ainda contém a resposta de antes de num chegar. Isso é exatamente can[i-1][s-num] da tabela, e a única linha dá conta do trabalho da tabela inteira.

Você também pode parar assim que reach[target] se tornar verdadeiro, porque os valores posteriores apenas acrescentam somas alcançáveis e nunca removem nenhuma. No pior caso, ainda são O(n × target) etapas, cerca de 2 × 10^6, e a memória cai para target + 1 valores booleanos.