Como Penso e Resolvo "Count Ways to Distribute Candies" em Elixir

Um Guia Completo da Força Bruta aos Números de Stirling

Na sequência do artigo anterior sobre Distribute Candies Among Children II, vamos agora encarar um problema que eleva a combinatória a outro patamar: Count Ways to Distribute Candies (LeetCode 1692). Enquanto o problema anterior lidava com doces idênticos e crianças distintas, este novo desafio nos apresenta doces únicos e sacos não vazios — uma mudança sutil que transforma completamente a natureza da contagem.

Este artigo percorre o mesmo processo mental: entender o problema, começar pela solução mais simples, encontrar a estrutura matemática subjacente e derivar uma solução ótima em Elixir. No caminho, vamos descobrir os Números de Stirling de Segunda Espécie — uma das sequências mais elegantes da combinatória.

O Problema

Existem n doces únicos (rotulados de 1 a n) e k sacos. Você deve distribuir todos os doces nos sacos de modo que cada saco tenha pelo menos um doce. Retorne o número de maneiras diferentes de distribuir os doces, módulo 10⁹ + 7.

Exemplos:

Input: n = 3, k = 2
Output: 3
Explanation: Você pode distribuir 3 doces em 2 sacos de 3 maneiras:
(1), (2,3)
(1,2), (3)
(1,3), (2)

Input: n = 4, k = 2
Output: 7
Explanation: Você pode distribuir 4 doces em 2 sacos de 7 maneiras.

Input: n = 20, k = 5
Output: 206085257
Explanation: 20 doces em 5 sacos: 1881780996 maneiras.
1881780996 mod (10⁹ + 7) = 206085257.

Constraints:

• 1 <= k <= n <= 1000

A assinatura em Elixir é:

defmodule Solution do
  @spec ways_to_distribute(n :: integer, k :: integer) :: integer
  def ways_to_distribute(n, k) do
    # implementação
  end
end

Passo 1: Entendendo o Problema — Doces Únicos e Sacos Não Vazios

A primeira diferença crucial em relação ao problema anterior é que os doces são únicos. Isso significa que distribuir o doce 1 no saco A e o doce 2 no saco B é diferente de distribuir o doce 1 no saco B e o doce 2 no saco A. A identidade dos doces importa.

A segunda diferença é que cada saco deve ter pelo menos um doce. Não podemos deixar sacos vazios.

A terceira diferença é que os sacos não são rotulados (a ordem dos sacos não importa). Ou seja, (1), (2,3) é o mesmo que (2,3), (1). O que importa é quais doces estão juntos no mesmo saco.

O Que Estamos Contando?

Estamos contando o número de partições de um conjunto de n elementos em exatamente k subconjuntos não vazios. Em matemática, esse número é conhecido como o Número de Stirling de Segunda Espécie, denotado por S(n, k) ou {n \brace k}.

Por exemplo, S(3, 2) = 3, que corresponde às três partições de {1, 2, 3} em dois subconjuntos não vazios:

• {1}, {2, 3}
• {1, 2}, {3}
• {1, 3}, {2}

Passo 2: Força Bruta — Gerando Todas as Partições

A abordagem mais simples é gerar todas as partições possíveis de n elementos em k subconjuntos não vazios e contar quantas existem. Isso pode ser feito recursivamente, mas o número de partições cresce muito rápido (o número de Bell, B(n), cresce super-exponencialmente), tornando inviável para n = 1000.

Implementação em Elixir (Inviável para n Grande)

defmodule Solution do
  def ways_to_distribute(n, k) do
    elementos = Enum.to_list(1..n)
    partitions(elementos, k)
    |> length()
    |> rem(1_000_000_007)
  end

  # Gera todas as partições de uma lista em exatamente k subconjuntos não vazios
  defp partitions([], 0), do: [[]]
  defp partitions([], _), do: []
  defp partitions(_list, 0), do: []

  defp partitions([h | t], k) do
    # Caso 1: h forma um novo subconjunto
    new_sets = partitions(t, k - 1) |> Enum.map(&[[h] | &1])

    # Caso 2: h é adicionado a um subconjunto existente
    existing_sets =
      partitions(t, k)
      |> Enum.flat_map(fn partition ->
        Enum.map(0..(k - 1), fn i ->
          List.update_at(partition, i, &[h | &1])
        end)
      end)

    new_sets ++ existing_sets
  end
end

Esta solução é exponencial e não passa para n = 1000. Precisamos de uma abordagem melhor.

Passo 3: A Recorrência dos Números de Stirling

A chave para resolver este problema eficientemente está na recorrência que define os Números de Stirling de Segunda Espécie. Considere o n-ésimo doce (o último a ser distribuído). Ele pode ser colocado de duas maneiras:

1. Em um saco sozinho: O doce n forma um novo saco. Os n-1 doces restantes são distribuídos em k-1 sacos. Isso dá S(n-1, k-1) maneiras.

2. Em um saco já existente: Os n-1 doces já estão distribuídos em k sacos, e o doce n pode ser colocado em qualquer um dos k sacos. Isso dá k × S(n-1, k) maneiras.

Portanto, a recorrência é:

S(n, k) = k × S(n-1, k) + S(n-1, k-1)

Casos Base

• S(n, n) = 1 — só há uma maneira de distribuir n doces em n sacos: cada doce no seu próprio saco.
• S(n, 0) = 0 para n > 0 — não há como distribuir doces em zero sacos.
• S(0, 0) = 1 — a partição vazia.
• S(n, k) = 0 se k > n — impossível ter mais sacos que doces (já que cada saco precisa de pelo menos um doce).

Passo 4: Programação Dinâmica — Bottom-Up

Com a recorrência em mãos, podemos construir uma tabela DP de baixo para cima. A tabela dp[i][j] representa S(i, j) — o número de maneiras de distribuir i doces em j sacos.

Implementação em Elixir

defmodule Solution do
  @mod 1_000_000_007

  @spec ways_to_distribute(n :: integer, k :: integer) :: integer
  def ways_to_distribute(n, k) do
    # Casos triviais
    cond do
      k > n -> 0
      k == n -> 1
      true -> build_dp(n, k)
    end
  end

  defp build_dp(n, k) do
    # dp[j] representa S(i, j) para o i atual
    # Inicialmente i = 0: dp[0] = 1 (partição vazia), dp[j] = 0 para j > 0
    initial_dp = List.duplicate(0, k + 1) |> List.replace_at(0, 1)

    # Iterar de i = 1 até n
    final_dp =
      Enum.reduce(1..n, initial_dp, fn i, dp ->
        # Para cada i, computar S(i, j) para j de min(i, k) até 1
        # S(i, j) = j * S(i-1, j) + S(i-1, j-1)
        max_j = min(i, k)

        1..max_j
        |> Enum.reduce(dp, fn j, acc ->
          valor = (j * Enum.at(acc, j) + Enum.at(acc, j - 1)) |> rem(@mod)
          List.replace_at(acc, j, valor)
        end)
      end)

    Enum.at(final_dp, k)
  end
end

Análise da complexidade:

• Tempo: O(n × k) — dois loops aninhados.
• Espaço: O(k) — usamos apenas um array unidimensional, atualizando-o a cada iteração de i.

Traçando n = 4, k = 2

i	dp[0]	dp[1]	dp[2]
0	1	0	0
1	1	1	0
2	1	1	1
3	1	1	3
4	1	1	7

Resultado: dp[2] = 7 ✓

Passo 5: Por Que a Ordem dos Sacos Não Importa?

Um ponto sutil é que os sacos não são rotulados. Na recorrência S(n, k) = k × S(n-1, k) + S(n-1, k-1), o fator k representa a escolha de qual saco existente receberá o novo doce. Mas se os sacos não são rotulados, por que podemos multiplicar por k?

A resposta é que, ao construir as partições indutivamente, os k sacos são tratados como distinguíveis temporariamente durante a construção. No entanto, a contagem final é independente da ordem, porque cada partição é contada exatamente uma vez: o doce n é adicionado ao saco que já contém o menor elemento (em alguma ordenação implícita). Isso é um resultado clássico da combinatória: os Números de Stirling de Segunda Espécie contam partições de conjuntos em subconjuntos não rotulados.

Passo 6: Alternativa — Top-Down com Memoização

Para quem prefere recursão com memoização, a mesma recorrência pode ser implementada de cima para baixo. Em Elixir, usamos um mapa como tabela de memoização.

defmodule Solution do
  @mod 1_000_000_007

  def ways_to_distribute(n, k) do
    do_ways(n, k, %{})
  end

  defp do_ways(n, k, memo) when k > n, do: 0
  defp do_ways(n, k, _memo) when k == n, do: 1
  defp do_ways(0, 0, _memo), do: 1
  defp do_ways(_, 0, _memo), do: 0

  defp do_ways(n, k, memo) do
    key = {n, k}

    case Map.get(memo, key) do
      nil ->
        result =
          (k * do_ways(n - 1, k, memo) + do_ways(n - 1, k - 1, memo))
          |> rem(@mod)

        {result, Map.put(memo, key, result)}

      cached ->
        {cached, memo}
    end
  end
end

Nota: A implementação acima tem um problema de threading do memo. Uma versão funcional correta precisaria retornar {resultado, memo} em todas as chamadas. Para simplificar, a versão bottom-up é mais idiomática em Elixir.

Passo 7: Comparando as Abordagens

Abordagem	Tempo	Espaço	Viável para n = 1000?
Força Bruta (gerar partições)	Exponencial	Exponencial	❌
DP Bottom-Up	O(n × k)	O(k)	✅
DP Top-Down com Memoização	O(n × k)	O(n × k)	✅

Para submissões no LeetCode, a solução DP Bottom-Up é a ideal porque é eficiente e usa espaço linear em k.

Passo 8: A Conexão com os Números de Stirling

Os Números de Stirling de Segunda Espécie S(n, k) aparecem em diversos contextos:

1. Partições de conjuntos: Número de maneiras de particionar um conjunto de n elementos em k subconjuntos não vazios.
2. Funções sobrejetoras: Número de funções sobrejetoras de um conjunto de n elementos para um conjunto de k elementos (quando os sacos são rotulados), dividido por k! para sacos não rotulados.
3. Momentos de distribuições: Aparecem no cálculo de momentos de distribuições de Poisson e binomial.
4. Polinômios de Bell: Os Números de Stirling são os coeficientes dos polinômios de Bell.

A fórmula explícita para S(n, k) é:

S(n, k) = (1/k!) × Σ_{j=0}^{k} (-1)^j × C(k, j) × (k - j)^n

Mas a recorrência é muito mais eficiente para computação.

Passo 9: O Modelo Mental — Resumo

O modelo mental que quero que você leve deste problema:

1. Reformule matematicamente: conte partições de um conjunto de n elementos em k subconjuntos não vazios.

2. Identifique a estrutura: reconheça que isso são os Números de Stirling de Segunda Espécie.

3. Encontre a recorrência: o último elemento pode formar um novo saco (S(n-1, k-1)) ou entrar em um saco existente (k × S(n-1, k)).

4. Implemente DP bottom-up: construa a tabela linha por linha, usando um array unidimensional para economizar espaço.

5. Aplique o módulo: como os números crescem muito rápido, aplique rem(10⁹ + 7) em cada passo.

6. Verifique com exemplos: trace os casos de teste dados.

7. Tenha um plano B: se a recorrência não for óbvia, a força bruta funciona para n pequeno.

Solução Completa em Elixir

defmodule Solution do
  @mod 1_000_000_007

  @spec ways_to_distribute(n :: integer, k :: integer) :: integer
  def ways_to_distribute(n, k) do
    cond do
      k > n -> 0
      k == n -> 1
      true -> build_dp(n, k)
    end
  end

  defp build_dp(n, k) do
    # dp[j] = S(i, j) para o i atual
    # Inicialmente i = 0: dp[0] = 1, dp[j] = 0 para j > 0
    initial_dp = List.duplicate(0, k + 1) |> List.replace_at(0, 1)

    final_dp =
      Enum.reduce(1..n, initial_dp, fn i, dp ->
        max_j = min(i, k)

        1..max_j
        |> Enum.reduce(dp, fn j, acc ->
          valor = (j * Enum.at(acc, j) + Enum.at(acc, j - 1)) |> rem(@mod)
          List.replace_at(acc, j, valor)
        end)
      end)

    Enum.at(final_dp, k)
  end
end

Traçando n = 4, k = 2:

• Inicial: [1, 0, 0]
• i=1: [1, 1, 0]
• i=2: [1, 1, 1]
• i=3: [1, 1, 3]
• i=4: [1, 1, 7]
• Resultado: 7 ✓

Por Que Esse Problema Importa

O problema Count Ways to Distribute Candies é mais que um desafio de programação dinâmica. É uma porta de entrada para os Números de Stirling, que aparecem em:

• Teoria dos grafos: contagem de grafos conexos.
• Probabilidade: momentos de distribuições.
• Análise de algoritmos: complexidade de algoritmos de particionamento.
• Física estatística: distribuições de Boltzmann.

A beleza deste problema está na transição do mundo dos doces idênticos (stars and bars) para o mundo dos doces únicos (Números de Stirling). Essa transição ilustra como pequenas mudanças nas premissas de um problema podem levar a estruturas matemáticas completamente diferentes.

Enquanto stars and bars conta soluções de equações, os Números de Stirling contam partições de conjuntos. Ambos são fundamentais, mas pertencem a ramos distintos da combinatória.

Conclusão

Este artigo completou a jornada iniciada no problema anterior. Começamos com doces idênticos e crianças distintas, usando stars and bars e inclusão-exclusão para obter uma solução O(1). Agora, com doces únicos e sacos não vazios, usamos os Números de Stirling de Segunda Espécie e programação dinâmica para obter uma solução O(n × k).

A lição mais importante é que a estrutura matemática do problema determina a técnica de solução. Identificar se os objetos são idênticos ou únicos, se os recipientes são rotulados ou não, e se há restrições de vazio ou capacidade é o primeiro passo para escolher a ferramenta combinatória correta.

Em Elixir, a solução DP bottom-up é concisa e eficiente, usando um array unidimensional para economizar espaço e Enum.reduce para expressar os loops aninhados de forma funcional. A recorrência S(n, k) = k × S(n-1, k) + S(n-1, k-1) traduz-se diretamente em código, tornando a implementação uma expressão direta da matemática subjacente.