| Español | English |
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.
Enumerar las particiones de un entero positivo parece una buena estrategia en la búsqueda de una solución, los elementos de una partición de un entero n suman exactamente n .
El número de particiones de un entero n , coincide con el coeficiente de x n en el desarrollo de la expresión,
Podemos expresar estas relaciones como un producto de binomios,
Esta última expresión será la herramienta que utilizaremos para resolver el problema de la suma de subconjuntos .
Determinar la existencia de solución se reduce a calcular el coeficiente de x n en el producto de binomios,
El coeficiente de x 27 es la unidad, de forma que existe una solución.
Nos preguntamos ahora sobre el número de elementos de cada subconjunto solución.
Utilizaremos una variable auxiliar que, a modo de testigo , llevará la cuenta de las cardinalidades.
El coeficiente de x 27 contiene al testigo a , con exponente tres, cardinalidad del único subconjunto solución.
Vamos a determinar los valores de cada subconjunto solución, para ello etiquetaremos cada variable testigo con un subíndice adecuado.
Subconjunto solución, { 5, 9, 13 }.
∎
| 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.
Enumerating integer partitions could be a technique to solving this problem, integers in a partition of n sum upto n .
The number of partitions of an integer n match the coefficient of x n in the expansion of expression,
We can transform this into a product of binomials,
This last expression will be the tool that we are using to solve the subset sum problem.
To decide if there is a solution mere calculate the coefficient of x n in the product of binomials,
Unity is the coefficient of x 27 so there is an only one solution.
We are asking now about number of integers in solution's subsets.
Using an auxiliar variable, like a marker , we can count solution subset's elements.
x 27 has as coefficient a with power index three, cardinality of the solution subset.
Members of each solution subset can be calculated tagging the auxiliary variables with a proper subindex.
Solution subset, { 5, 9, 13 }.
∎
