/*
Program: partition-integer.c (Report comments/bugs to chikh@yuntech.edu.tw)
Function: 以遞迴的方式對給定的某一正整數進行分割，並列出所有可能的分割形式。例如：4 = 4+0
		  = 1+3 = 2+2 = 1+1+2 = 1+1+1+1共有5種分法。 
		  運作理念：設待分割的數為n、max為最大元素值(max<=n，形成分割的每一個元素i<=max)，
		  由1開始遞增決定一數值i視為此次所採分解元素，並把i存入堆疊，此時待分割的數即變成 
		  (n-i)，如此再依上述邏輯繼續分割，直至無法分割(觸底)為止。一旦觸底即把過去儲存
		  在堆疊中的元素逐一提取出來並顯示於螢幕。每一次觸底，意味著一種連續分割方式暫告
		  一段落，程式應返回至最近啟動連續分割之上層流程位置，再繼續處理未決的部分，直至
		  所有可能的分割方式均已探索過，整個問題方告完畢 
Notes: 1) 留意遞迴函數的呼叫方式、參數與順序，有點小複雜但應不難懂，另注意一旦觸底的應
		  對機制 
	   2) 運用堆疊的概念順應遞迴呼叫的特性，逐筆紀錄分割過程所採之分解元素
	   3) 參考並修改 https://bit.ly/3dC2mlX 所載版本 
*/

#include <stdio.h>

int indx = 0;	/* 索引，指示堆疊頂端元素位置 */			
int element[100] = {0};  /* 以陣列實作堆疊結構 */ 

void printPartitions(int n, int max, int addend) /* n:待分割的數、max:最大元素、addend:所採用的分解元素 */
{
	int i;
	
	element[indx++] = addend;	/* 相當於push()動作 */ 
    	
    if (n == 0) { /* 已觸底、無法再分割 */ 
    	for (i = indx-1; i > 0; i--) /* 把推疊紀錄的元素逐一印出 */ 
    		printf("%d ",element[i]);
    	printf("\n");
	}
    else /* n > 0，意味著尚可繼續分割 */ 
       	for (i = 1; i <= max && i <= n; i++) /* 由1開始遞增決定一數值i視為此次所採分解元素，待分割的數即變成(n-i) */
       		printPartitions(n-i,i,i); //printPartitions(target-i,i,element[indx++]=i);
    
	indx--;	/* 等同pop()動作 */ 
}

int main()
{
	int n; 
	
	printf("輸入欲分割的正整數 ==> ");
	scanf("%d",&n);
	printf("可能的分割方式如下：\n");
	printPartitions(n,n,0); 
	
	return 0;
}