蓝点杯 打印整数划分问题

正整数n可能存在不同的划分，例如正整数6的全部划分为

6=6

6=5+1

6=4+2     6=4+1+1

6=3+3       6=3+2+1       6=3+1+1+1

6=2+2+2   6=2+2+1+1   6=2+1+1+1+1

6=1+1+1+1+1+1

在王晓东的书上有关本题的递归公式，但公式不好推，而且求的只是方案个数不满足本题题意。

仔细会发现其实本题就是一颗树。dfs+剪枝+数组保存轻松解决。

public class Spit
{
	static int sum=0,num=0;
	static int t[]=new int[121];
	static void dfs(int n,int m)
	{
		if(sum==m)
		{
			System.out.print(m+"=");
			for(int k=1;k<n-1;k++)
				System.out.print(t[k]+"+");
			System.out.println(t[n-1]);
			num++;
		}
		else
		{
			for(int i=m-n+1;i>=1;i--)
			{
				sum+=i;
				if(sum<=m)
				{
					if(i<=t[n-1])
					{
						t[n]=i;
						dfs(n+1,m);
					}
				}	
				sum-=i;
			}
		}
	}
	public static void main(String args[])
	{
		Scanner cin=new Scanner(System.in);
		while(cin.hasNext())
		{
			int n=cin.nextInt();
			t[0]=120;
			dfs(1,n);
			System.out.println("一共有"+num+"方案.");
			num=0;
		}
	}
}