n个球中不放回取出m个：(利用递归解决问题)
抓住关系：
设一个特定球为i
分为两种情况：
- 要取球i，则需要在剩下n-1个球中取m-1个球，不取球i，则需要在剩下n-1个球中取出m个球。
f(n ,m)= f(n-1,m-1)+f(n-1,m);//取了特定球与没取特定球总数之和
public static int f(int n ,int m) {
if (n==m) return 1;//n个球中取n个
if (n
2. 全排列的输出
试探与回溯的思想，将n个数n！中全排列方式罗列出来
public static void f(char[] data ,int k) {
//使k为基准值，与后一元素交换
if(k==data.length)
System.out.println(String.valueOf(data));//输出
for(int i=k;i
3.李白打酒：（类似二项分布）
初始酒两斗，遇店加一倍，遇花喝一斗，经过15个地点(最后肯定经过花)，恰好喝完，列出所有情况。
static char[] string=new char[17];
static int sum=0;
public static void main(String[] args) {
fun(2, 1, 0, 0);
}
public static void fun(int drink,int index,int num_dian,int num_hua) {
if(drink<0||index>16||(drink==0&&index<16)) {
return;
}
if(index==16&&drink==0) {
System.out.println(sum+++" "+String.valueOf(string));
return;
}
string[index-1]='店';
fun(drink*2, index+1, num_dian+1, num_hua);
string[index-1]='花';
fun(drink-1, index+1, num_dian, num_hua+1);
}
4. 集合划分
n 个元素的集合{1,2,…, n }可以划分为若干个非空子集。例如，当 n=4 时，集合{1，2，3，4}可以划分为 15 个不同的非空子集如下：
{{1}，{2}，{3}，{4}}，
{{1，2}，{3}，{4}}，
{{1，3}，{2}，{4}}，
{{1，4}，{2}，{3}}，
{{2，3}，{1}，{4}}，
{{2，4}，{1}，{3}}，
{{3，4}，{1}，{2}}，
{{1，2}，{3，4}}，
{{1，3}，{2，4}}，
{{1，4}，{2，3}}，
{{1，2，3}，{4}}，
{{1，2，4}，{3}}，
{{1，3，4}，{2}}，
{{2，3，4}，{1}}，
{{1，2，3，4}}
思路
1.先想几种小的情况:
1）m=n的情况，结果很明显是1。
2）m=1的情况，结果也是1。
2.把多的情况转换成小的
1）把前n-1个元素分成m-1份，然后n号元素单独放。
2）把前n-1个元素分成m份，然后把n号元素插入到这m个集合中（有m种插法）
总数就是
F(n,m) =F(n-1,m-1) + m * F(n-1,m)
代码：
利用递归方法。
public static void main(String[] args) {
int count=0;
for(int i=1;i<=4;i++)
count+=F(4,i);
System.out.println(count);
}
public static int F (int n,int m) {
if(m==1||m==n)
return 1;
else {
return F(n-1,m-1)+m*F(n-1,m);
}
}
利用递推方法：
public static void main(String[] args) {
int a[][]=new int[5][5];
a[0][0]=1;
for(int i=1;i<=4;i++) {
for (int j = 1; j <= i; j++) {
a[i][j]=a[i-1][j-1]+j*a[i-1][j];
}
}
for (int i = 0; i < a.length; i++) {
for (int j = 0; j < a.length; j++) {
System.out.print(a[i][j]+" ");
}
System.out.println();
}
}
得到输出为：
1 0 0 0 0
0 1 0 0 0
0 1 1 0 0
0 1 3 1 0
0 1 7 6 1
引申
若有相同元素的集合分组问题
