Dada n que va de 1 a 100, encontrar la suma de dígitos igual a la mitad de la suma aritmética de 1 a 100

Question

Tengo una secuencia de números del 1 al 100. Dados dos contenedores, los números se asignan al azar a cada contenedor.

Sé que la suma total de 1 a 100 es 5050. Por lo tanto, para que ambos recipientes tengan la misma suma, cada recipiente debe sumar hasta 2525. Todos los 100 números deben pertenecer a cualquiera de las dos cajas.

Sé que hay un total de 2^100 combinaciones posibles. ¿Cómo encuentro el número de combinaciones que suman 2525 en cada recipiente?

Gracias.

EDITAR: Para que quede claro, una papelera es sólo una colección de números. Así que esencialmente, tengo la colección A y la colección B. La suma de cada colección debe ser igual y los 100 números deben pertenecer a cualquiera de las dos. Piensa en ellos como cubos o lo que sea conveniente para la explicación.

Answer 1

Utilizando la recursión (gracias Bilou06)

$$f(n, S) = f(n - 1, S) + f(n - 1, S - n),$$

tenemos el siguiente código Python:

n = 100
S = 2525

matrix = [[0]*(S+1) for x in range(0, n+1)]

for S in range(0, S+1):
    matrix[0][S] = 0
for n in range(0, n+1):
    matrix[n][0] = 1
for n in range(1, n+1):
    for S in range(S+1):
        matrix[n][S] = matrix[n-1][S] + matrix[n-1][S-n]

print matrix[n][S]

Puede cambiar los valores de n y S cuando se ejecuta el código para verificar que funcionan para los casos más pequeños.

Answer 2

He convertido el código a código c. Sin embargo, mi código se cuelga.

lo he intentado con un valor menor de n =15. pero mi código c produce 5505 en lugar de los 722 que produce este código python.

#include <stdio.h>
#include <string.h>
#include <math.h>  main() 
{ 
 int n=100; 
 double k=2; 
 int min=2525; 
 int rec[100][2525]; //100 row, 2525 column
 int x,y,r,c,str; 
 int po = (int) pow((double) k,n); //2^100

for (r=0;r<n+1;r++) {
    for(c=0;c<min+1;c++)
    {
        rec[r][c]=0;
    } } for (x=0;x<n+1;x++) {
    rec[x][0]=1; }

for (y=0;y<min+1;y++) {
    rec[0][y]=0; }

for (r=1;r<n+1;r++) {
    for(c=0;c<min+1;c++)
    {
        rec[r][c]=rec[r-1][c]+rec[r-1][c-r];
    } }

printf("%d, %d, %d\n",rec[100][2525],r,c); printf("%d", po ); scanf ("%d",str); }