给你一个小于50的数字 a ，请写出一个算法得到所有可能的数字集合，每个数字集合满足以下条件：
1. 集合中所有数字的和等于a;
2. 集合中的所有数字均大于1；
3. 集合中可以出现重复数字；
例如：
2 -> {2},
3->{3},
4->{[4], [2, 2]},
5->{[5], [3, 2]},
6->{[6], [4, 2], [3, 3], [2, 2, 2]}
7->{[7], [5, 2], [4, 3], [3, 2, 2]}
8->{[8], [6, 2], [5, 3], [4, 4], [4, 2, 2], [3, 3, 2], [2, 2, 2, 2]}

1. import java.util.Scanner;
   
2. public class bp
   
3. {
   
4.         static int n;
   
5.         static int count=0;//count为统计集合元素的个数
   
6.         static int []d=new int[25];//存放集合中的每个元素
   
7.         static void divide(int number,int idx)
   
8.         {
   
9.                 if(number==0)
   
10.                 {               
    
11.                         if(count==0)
    
12.                         {
    
13.                                 System.out.print(n+"->");
    
14.                                 System.out.print("{");
    
15.                         }
    
16.                         for(int i=0;i<idx;i++)
    
17.                         {
    
18.                                 if(i==0&&(n/2>1))
    
19.                                         System.out.print("[");
    
20.                                 if(i>0)
    
21.                                         System.out.print(",");
    
22.                                 System.out.print(d[i]);
    
23.                         }
    
24.                         if(n/2>1) System.out.print("]");
    
25.                         if(idx<n/2)
    
26.                                 System.out.print(",");
    
27.                         else
    
28.                                 System.out.println("}");
    
29.                         count++;//元素个数自增
    
30.                         return;
    
31.                 }
    
32.                 for(int i=number;i>=2;i--)//从大到小开始选数
    
33.                 {
    
34.                         if(idx==0||i<=d[idx-1])//用来保证右边的数不大于左边的
    
35.                         {
    
36.                                 d[idx]=i;
    
37.                                 divide(number-i,idx+1);//递归
    
38.                         }
    
39.                 }
    
40.         }
    
41.         public static void main(String[] args)
    
42.         {
    
43.                 Scanner sc=new Scanner(System.in);
    
44.                 while(sc.hasNextInt())
    
45.                 {
    
46.                         count=0;
    
47.                         n=sc.nextInt();
    
48.                         divide(n,0);//递归
    
49.                 }       
    
50.         }
    
51. }

复制代码

运行结果如下：2
2->{2}
3
3->{3}
4
4->{[4],[2,2]}
5
5->{[5],[3,2]}
6
6->{[6],[4,2],[3,3],[2,2,2]}
7
7->{[7],[5,2],[4,3],[3,2,2]}
8
8->{[8],[6,2],[5,3],[4,4],[4,2,2],[3,3,2],[2,2,2,2]}
不会上传截图

file:///C:/1.jpg

这类问题统称背包问题，即求容量为a的背包，完全装满的方案。  代码中的n应该改成a的。忘记改了，不影响结果。
我们老师带我们参加软件大赛，辅导课时讲了这类问题的解法，分0/1背包和完全背包讲的，所以此类题对我来说毫无压力，呵呵！
解法思路就是：递归，从大到小选数，若选出来的数和正好为a，则输出一种方案。