Algoritmo para dividir un número en un grupo ordenado diferente de modo que la suma de esos números sea el número original

¿No necesita ser eficiente? Genial, puedo manejar eso.

1. Calcule el número de particiones por cualquier medio que desee, por ejemplo, utilizando la fórmula
   Crea una matriz vacía de este tamaño.
2. Si la matriz está llena, finalice y envíe los datos en la matriz de manera adecuada.
3. Genere una lista aleatoria de n enteros no negativos entre 0 y n .
4. Si la lista suma n , y aún no está en la matriz (hasta la permutación), agréguela a la matriz.
5. Ve al paso 3.

Crédito adicional: calcule el tiempo de ejecución asintótico de este algoritmo en función de n .

Si la fórmula en la parte (1) parece demasiado trabajo para calcular de manera efectiva, puede interesarle la observación de Ivan Li en los comentarios.

Un enfoque menos matemático y más de fuerza bruta (dado que el matemático ya ha sido respondido) sería probarlos en orden lexicográfico (o alfabético). Entonces nuestra salida sería como:
[1, 1, 1, 1]
[1, 1, 2]
[1, 2, 1]
[1, 3]
[2, 1, 1]
[2, 2]
[3, 1]
[4]

Sea n el número principal.

Comenzamos con una matriz vacía []. En cada paso, pasamos a la siguiente matriz en orden alfabético. Es útil pensar en alfabetos. a es la primera palabra, aa sería la siguiente y así sucesivamente. Así que seguimos agregando 1s a la matriz hasta llegar a una matriz cuyo total es n.

Cuando alcanzamos una matriz de este tipo, no agregamos más 1s, ya que sería inútil. Lo que debemos hacer es ir a la siguiente matriz posible que tenga un total menor o igual que n. Entonces, eliminamos el último elemento de la matriz y aumentamos el valor del segundo último elemento en 1.

Entonces nuestro algoritmo es bastante simple:

  A = []
 mientras que A! = [n]
   si suma (A) 
  Si desea hacerlo más rápido, puede administrar de manera más inteligente cuántos 1s agrega, cómo calcula la suma, cómo cambia el tamaño de las matrices, etc.  Una vez optimizado, esto puede ser tan rápido como cualquier otro algoritmo aquí, lineal en el número de elementos en la salida. 
  Es de suma importancia que se entienda el algoritmo y que cualquier optimización también se entienda antes de la codificación.  Y aunque este es un enfoque rápido válido, recomiendo que cualquier lector también comprenda los conceptos involucrados en el enfoque combinatorio y los detalles técnicos de la implementación de Ivan. 
  EDITAR: ahora que la pregunta se ha editado pidiendo grupos no ordenados también, esta edición es para agregar ese aspecto. 
  Para grupos desordenados, es suficiente que solo observemos las matrices ordenadas lexicográficamente.  Y una condición suficiente para que se ordene una matriz es que el elemento después de un número específico tiene que ser mayor o igual a ese número. 
  Entonces, reescribiendo el algoritmo para agregar un elemento que lo haga ordenado en lugar de agregar 1: 
  A = []
 mientras que A! = [n]
   if sum (A) + A.lastElement <= n:
     A.append (A.lastElement)
   más si suma (A) 
  Las únicas operaciones realizadas anteriormente son: 
  Agregar el último número a la matriz si no hace que la suma exceda n (permanece ordenada) 
  Si lo hace exceder n, aumente el último número para que la suma sea igual a n.  (todavía ordenado) 
  Si es n, elimine el último elemento y aumente el nuevo último elemento (nuevamente, ordenado) 
  Se necesita un poco más de discusión para ver que no se deja fuera una matriz válida clasificada lexicográficamente, pero no es demasiado difícil ver eso. 

    

Podemos pensar en dividir un número en grupos como colocar separadores entre una secuencia de objetos. Por ejemplo, dividiríamos 4 objetos en grupos:

X X X X

Podemos separarlos de esta manera

X | X X | X

y obtener 3 grupos con tamaños 1,2,1 respectivamente, o separarlos de esta manera

X X | X X

y obtener 2 grupos con tamaños 2,2. Como hay 3 lugares donde podemos colocar los separadores, la cantidad de formas es [matemática] 2 ^ 3 = 8 [/ matemática] (o 7 si no se permite usar solo un grupo).

En el siguiente programa, las posiciones de los separadores se codifican en un número entero b, donde cada bit de b representa si hay un separador en la posición correspondiente.

#include int main(){ int n, b, i, c; scanf("%d", &n); for(b=0; b<(1<<(n-1))-1; b++){ c = 0; for(i=0; i