No problema clássico de soma de subconjuntos, há um conjunto S e um alvo t, e o objetivo é encontrar um subconjunto de S cuja soma seja t. Esta variante tem uma solução em tempo pseudopolinomial.
Em uma variante do problema da soma de subconjuntos, o objetivo é encontrar todos os subconjuntos de S cuja soma é t. Esta variante não possui solução em tempo pseudopolinomial; veja as respostas aqui: Obtendo todos os subconjuntos do problema da soma de subconjuntos em Python usando Programação Dinâmica . Um dos comentários explica que, no pior caso, quando você tem N zeros e a soma necessária também é zero, você precisará gerar todos os 2^n - 1 subconjuntos - portanto, não é possível obter um resultado melhor que O(2^n).
E se não diferenciarmos entre dois itens do mesmo valor (de modo que, se dois conjuntos forem compostos de alguns itens com os mesmos valores, eles serão considerados o mesmo conjunto) --- qual é a complexidade de tempo de execução para gerar todos os diferentes subconjuntos com soma t?