Soma de Combinações (Combination Sum)

Dado o valor-alvo N e um array de números positivos permitidos, você deve contar de quantas maneiras é possível escrever N como a soma desses números.

Por exemplo, se os valores permitidos forem [1, 2, 3] e N for 4, podemos somar esses números de 7 maneiras diferentes:

Todas as 7 maneiras de somar 1, 2, 3 para chegar a 4

1 + 1 + 1 + 1

1 + 1 + 2

1 + 2 + 1

2 + 1 + 1

1 + 3

3 + 1

2 + 2

Este é um problema clássico de programação dinâmica, que pode ser resolvido mantendo um estado d[sum], representando todas as formas possíveis de obter sum combinando os números permitidos:

N = ...
nums = [...]
d = [0] * (N + 1)          # d[i] = todas as combinações que resultam em i
d[0] = 1                   # Existe 1 maneira de obter 0 - não usar nenhum número

for i in range(1, N + 1):  # Tentar obter todos os valores de 1 até N
    for num in nums:       # Tentar construir d[i] com a ajuda de num
        if i - num >= 0:   # Se for possível obter i a partir de num
            d[i] += d[i - num]
print(d[N])

Assim, nosso estado d[i] é o número de maneiras de formar i usando os números em nums. Inicializamos tudo com 0, exceto d[0], que definimos como 1, pois há apenas uma forma de se obter 0 — não usar nenhum dos números permitidos. Para todos os outros valores, olhamos para todas as maneiras possíveis de obter esses números usando nums.

Por exemplo, se já houver 5 maneiras de chegar a 11 (d[11]) e 3 maneiras de chegar a 8 (d[8]), e se o número 3 estiver em nums, então todas as 3 maneiras de chegar a 8 contribuem para novas formas de chegar a 11 (basta adicionar o 3).

Vamos simular o algoritmo com a entrada de exemplo:

nums = [1, 2, 3] e N = 4

d = [1, 0, 0, 0, 0] → 1 maneira de obter 0, e as demais posições valem 0

i = 1num = 1 ⇒ d[1] += d[0] ⇒ d = [1, 1, 0, 0, 0] num = 2 ⇒ i - num < 0 num = 3 ⇒ i - num < 0

i = 2num = 1 ⇒ d[2] += d[1] ⇒ d = [1, 1, 1, 0, 0] num = 2 ⇒ d[2] += d[0] ⇒ d = [1, 1, 2, 0, 0] num = 3 ⇒ i - num < 0

i = 3num = 1 ⇒ d[3] += d[2] ⇒ d = [1, 1, 2, 2, 0] num = 2 ⇒ d[3] += d[1] ⇒ d = [1, 1, 2, 3, 0] num = 3 ⇒ d[3] += d[0] ⇒ d = [1, 1, 2, 4, 0]

i = 4num = 1 ⇒ d[4] += d[3] ⇒ d = [1, 1, 2, 4, 4] num = 2 ⇒ d[4] += d[2] ⇒ d = [1, 1, 2, 4, 6] num = 3 ⇒ d[4] += d[1] ⇒ d = [1, 1, 2, 4, 7]

print(d[4]) → imprime 7

Desafio – Combinações de Dados

Se você jogar um dado, ele produz um número de 1 a 6. Você precisa determinar o número de maneiras de obter o valor n somando lançamentos desse dado.

Entrada

A entrada contém um único inteiro n (1 ≤ n ≤ ).

Saída

O programa deve imprimir o número de maneiras de lançar o dado para obter a soma n. Como a resposta pode ficar muito grande, você deve exibi-la módulo .

Exemplos

Entrada	Saída
2	2
3	4

Explicação

2 → 1 + 1, 2

3 → 1 + 1 + 1, 1 + 2, 2 + 1, 3

Desafio – Combinações de Dados

Entrada

Saída

Exemplos

Explicação

Constraints

To check your solution you need to sign in

Sign in to continue