O problema de soma do subconjunto estados:

ado um conjunto de números inteiros, existe um subconjunto não vazio cuja soma é zer

Este problema é NP-completo em geral. Estou curioso para saber a complexidade dessa pequena variante:

Dado um conjunto de números inteiros, existe um subconjunto de tamanhok cuja soma é zero?

Por exemplo, sek = 1, você pode fazer uma pesquisa binária para encontrar a resposta emO(log n). E sek = 2, você pode reduzi-lo paraO(n log n) (por exemplo, consulte Encontre um par de elementos de uma matriz cuja soma seja igual a um determinado número). E sek = 3, então você pode fazerO(n^2) (por exemplo, consulteEncontrando três elementos em uma matriz cuja soma é a mais próxima de um determinado número).

Existe um limite conhecido que pode ser colocado nesse problema em função dek?

Como motivação, eu estava pensando sobre esta questãoComo você particiona uma matriz em 2 partes, de modo que as duas partes tenham média igua e tentando determinar se é realmente NP-completo. A resposta está em saber se existe ou não uma fórmula descrita acim

Com uma solução geral, eu estaria muito interessado em conhecer um limite ótimo parak=4.