Suma  de  subconjuntos.  Enumeración. Subset  sum.  Enumeration.⠀⠀⠀...

Español

Dado un conjunto arbitrario de enteros,

¿ Existe un subconjunto cuya suma sea exactamente un valor dado ?

ℤ⁺

En esta ocasión nos vamos a ocupar de una versión del problema enunciado, restringiendo el conjunto de partida a los enteros positivos.

Este problema puede abordarse en el contexto de las particiones de enteros, ver [suma_de_subconjuntos@j2e2xae] , pero en este caso vamos a solucionarlo en la forma de una recurrencia.

Recurrencia

⑴

⑵

⒜

⒝

⌘

Dados un conjunto de enteros positivos S = { a₁, a₂, ... a_m } y un entero positivo k,

∑ a > k
^m

Definimos una función F , con valor el número de subconjuntos de S con suma k .

F ( n₁,n₂...n_m; k )

n_m < k ∀ m

Si quitamos el elemento n_m, el subconjunto resultante da lugar a dos opciones para la realización de la suma, puedes elegir entre k y k − n_{m .}

F ( n₁,n₂...n_m; k ) = F ( n₁,n₂...n_m-1; k − n_m ) + F ( n₁,n₂...n_m-1; k )

Hemos determinado una relación de recurrencia que nos permite resolver el problema de dimensión ( m, k ) con las soluciones en ( m  − 1,  k  − n_m ) y ( m  − 1,  k  ).

Teniendo en cuenta las igualdades siguientes,

F (⋯ ; 0 ) = 0

F (⋯ k ⋯ ; k ) = 1 + F (⋯ ; k )

∑ S < k ⇒ F (S ; k ) = 0

∑ S = k ⇒ F (S ; k ) = 1

Podemos construir una solución recursiva ⒜ , ⒝
con casos base, ecuación ⒜ ,( ∅ , k ) y ( S , 0 ),
que ha de conservar las propiedades ⑴ y ⑵ .

Ordenar los elementos del conjunto de forma ascendente facilita la tarea de verificar las propiedades.

Ejemplo

S = { 1, 2, 3, 5, 10, 15, 20, 50 }, k = 73

∑ (1, 2, 3, 5, 10, 15, 20, 50) > 73

F (1, 2, 3, 5, 10, 15, 20, 50; 73) =
F₁ (1, 2, 3, 5, 10, 15, 20; 23) +
F₂ (1, 2, 3, 5, 10, 15, 20; 73)

F₁: ∑ (1, 2, 3, 5, 10, 15, 20) > 23
F₁ (1, 2, 3, 5, 10, 15, 20; 23) =
F₁₁ (1, 2, 3, 5, 10, 15; 13) +
F₁₃ (1, 2, 3, 5, 10, 15; 23)

F₁₁ (1, 2, 3, 5, 10, 15; 13) = F₁₁ (1, 2, 3, 5, 10; 13)
∑ (1, 2, 3, 5, 10) > 13
F₁₁ (1, 2, 3, 5, 10; 13) =
F₂₁ (1, 2, 3, 5; 3) +
F₂₃ (1, 2, 3, 5; 13)

F₂₁ (1, 2, 3, 5; 3) = F₂₁ (1, 2, 3; 3)
F₂₁ (1, 2, 3; 3) = 1 + F₃₃ (1, 2; 3)
⋮
F₂₁ (1, 2, 3, 5; 3) = 2
F₂₃ (1, 2, 3, 5; 13) = 0
F₁₁ (1, 2, 3, 5, 10; 13) = 2
F₁₃ (1, 2, 3, 5, 10, 15; 23) = 2
F₁ (1, 2, 3, 5, 10, 15, 20; 23) = 4
F₂ (1, 2, 3, 5, 10, 15, 20; 73) = 0

F (1, 2, 3, 5, 10, 15, 20, 50; 73) = 4 + 0 = 4

∎

English Español

An integer set given,
Is there any subset that sums precisely upto other integer ?

ℤ⁺

We restrict our attention to a variant of this problem involving positive integers only.

This problem could be solved as an integer partitions one, see [subset_sum@j2e2xae], now we are solving it by a recurrence relation.

Recurrence

⑴

⑵

⒜

⒝

⌘

Given a positive integer set S = { a₁, a₂, ... a_m } and a positive integer k,

             ∑ a   >   k
^m

A function defined F , with value the number of S subsets that sum upto k .

F ( n₁,n₂...n_m; k )

n_m < k ∀ m

Drop n_m, remaining subset has two options to sum, k or ( k − n_m ),

F ( n₁,n₂...n_m; k ) = F ( n₁,n₂...n_m-1; k − n_m ) + F ( n₁,n₂...n_m-1; k )

That is a recurrence relation that solves the problem ( m, k ) using solutions ( m  − 1,  k  − n_m ) and ( m  − 1,  k  ).

Note the equalities,

F (⋯ ; 0 ) = 0

F (⋯ k ⋯ ; k ) = 1 + F (⋯ ; k )

∑ S < k ⇒ F (S ; k ) = 0

∑ S = k ⇒ F (S ; k ) = 1

We can build a recursive solution ⒜ and ⒝,
with base cases, ( ∅ , k ) and ( S , 0 ), in equation ⒜
and an invariant as properties ⑴ and ⑵ .

Ascendig ordering makes verifying invariant properties easier.

Example

S = { 1, 2, 3, 5, 10, 15, 20, 50 }, k = 73

∑ (1, 2, 3, 5, 10, 15, 20, 50) > 73

F (1, 2, 3, 5, 10, 15, 20, 50; 73) =
F₁ (1, 2, 3, 5, 10, 15, 20; 23) +
F₂ (1, 2, 3, 5, 10, 15, 20; 73)

F₁: ∑ (1, 2, 3, 5, 10, 15, 20) > 23
F₁ (1, 2, 3, 5, 10, 15, 20; 23) =
F₁₁ (1, 2, 3, 5, 10, 15; 13) +
F₁₃ (1, 2, 3, 5, 10, 15; 23)

F₁₁ (1, 2, 3, 5, 10, 15; 13) = F₁₁ (1, 2, 3, 5, 10; 13)
∑ (1, 2, 3, 5, 10) > 13
F₁₁ (1, 2, 3, 5, 10; 13) =
F₂₁ (1, 2, 3, 5; 3) +
F₂₃ (1, 2, 3, 5; 13)

F₂₁ (1, 2, 3, 5; 3) = F₂₁ (1, 2, 3; 3)
F₂₁ (1, 2, 3; 3) = 1 + F₃₃ (1, 2; 3)
⋮
F₂₁ (1, 2, 3, 5; 3) = 2
F₂₃ (1, 2, 3, 5; 13) = 0
F₁₁ (1, 2, 3, 5, 10; 13) = 2
F₁₃ (1, 2, 3, 5, 10, 15; 23) = 2
F₁ (1, 2, 3, 5, 10, 15, 20; 23) = 4
F₂ (1, 2, 3, 5, 10, 15, 20; 73) = 0

F (1, 2, 3, 5, 10, 15, 20, 50; 73) = 4 + 0 = 4

∎

Media Public domain, via Wikimedia Commons

Suma de subconjuntos. Enumeración. Subset sum. Enumeration.⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀

Dado un conjunto arbitrario de enteros,

¿ Existe un subconjunto cuya suma sea exactamente un valor dado ?

ℤ+

Recurrencia

∑ a > km

F ( n1 ,n2 ...nm ; k )nm < k ∀ m

F ( n1 ,n2 ...nm ; k ) = F ( n1 ,n2 ...nm-1 ; k − nm ) + F ( n1 ,n2 ...nm-1 ; k )

F (⋯ ; 0 ) = 0 F (⋯ k ⋯ ; k ) = 1 + F (⋯ ; k )∑ S < k ⇒ F (S ; k ) = 0∑ S = k ⇒ F (S ; k ) = 1

Ejemplo

An integer set given,

Is there any subset that sums precisely upto other integer ?

ℤ+

Recurrence

∑ a > km

F ( n1 ,n2 ...nm ; k )nm < k ∀ m

F ( n1 ,n2 ...nm ; k ) = F ( n1 ,n2 ...nm-1 ; k − nm ) + F ( n1 ,n2 ...nm-1 ; k )

F (⋯ ; 0 ) = 0 F (⋯ k ⋯ ; k ) = 1 + F (⋯ ; k )∑ S < k ⇒ F (S ; k ) = 0∑ S = k ⇒ F (S ; k ) = 1

Example

Suma  de  subconjuntos.  Enumeración. Subset  sum.  Enumeration.⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀

ℤ⁺

∑ a > k
^m

F ( n₁,n₂...n_m; k )

n_m < k ∀ m

F ( n₁,n₂...n_m; k ) = F ( n₁,n₂...n_m-1; k − n_m ) + F ( n₁,n₂...n_m-1; k )

F (⋯ ; 0 ) = 0

F (⋯ k ⋯ ; k ) = 1 + F (⋯ ; k )

∑ S < k ⇒ F (S ; k ) = 0

∑ S = k ⇒ F (S ; k ) = 1

ℤ⁺

∑ a > k
^m

F ( n₁,n₂...n_m; k )

n_m < k ∀ m

F ( n₁,n₂...n_m; k ) = F ( n₁,n₂...n_m-1; k − n_m ) + F ( n₁,n₂...n_m-1; k )

F (⋯ ; 0 ) = 0

F (⋯ k ⋯ ; k ) = 1 + F (⋯ ; k )

∑ S < k ⇒ F (S ; k ) = 0

∑ S = k ⇒ F (S ; k ) = 1