（Java实现） 自然数的拆分

题目描述

任何一个大于1的自然数n，总可以拆分成若干个小于n的自然数之和。拆分成的数字相同但顺序不同被看做是相同的方案，如果1+3与3+1被看做是同一种方案。

输入

输入待拆分的自然数n。

输出

如样例输出若干个拆分方案(具体见样例)。

样例输入

7

样例输出

1+1+1+1+1+1+1
1+1+1+1+1+2
1+1+1+1+3
1+1+1+2+2
1+1+1+4
1+1+2+3
1+1+5
1+2+2+2
1+2+4
1+3+3
1+6
2+2+3
2+5
3+4

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Scanner;
import java.util.Set;


public class ziranshudechaifenwenti {
	public static int n,count=0,sum=0;
	public static ArrayList<Integer> list = new ArrayList<Integer>();
	public static Set<String> set = new HashSet<String>();
	public static void main(String[] args) {
		Scanner sc =new Scanner(System.in);
		n = sc.nextInt();
		f(0);
		Iterator it = set.iterator();
	while(it.hasNext()){
		
			System.out.println(it.next());
		}
		System.out.println(count);
	}
	public static void f(int a){
		if(a==n){
			if(list.size()==1) return;//把他本身删去
			count++;
			String s = "";
			for (int i = 0; i < list.size(); i++) {
				s=s+list.get(i);
			}
			
			set.add(s);
			return;
		}
		
		for (int i = 1; i <=n; i++) {
			if(a+i>n) continue;
			if( list.size()==0 || list.get(list.size()-1)<=i ){
				list.add(i);
				a+=i;
				f(a);
				list.remove(list.size()-1);
				a-=i;
			}
		}
	}

}