（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;

			}

		}

	}

}