组合算法

在数学中，我们学习了，排列组合，排列是有序的，组合是无顺序的。在做算法题时，我们也会遇到这种。
so，今天来理下，怎么写组合。

举个例子，桌子上有3个球A,B,C，我们取2个，无放回的取，有几种情况？算一下：也就是C(3,2)=3。

需要解决的问题

那么先理下思路，我们需要解决哪几个问题：

1. 要怎么表示3个数是否被取了呢，我想，弄一个int数组把他们的初值置为0，就像int a = {0,0,0},如果他被取了，就把它置为1，三个int分别代表ABC。
2. 然后就是从箱子里取球,是组合是吧。
3. 最后，满足条件，输出我们得到的组合。

方案

第一步，我们已经解决了，怎么表示球被取出来了。
第二步，组合：
我们想下，以下场景：

• 从桌子上取A，那么就是BC求组合，取B，就是AC求组合，取C，就是AB求组合
• 继续重复，求BC的组合，就是取B出来，求C的组合，再像这样继续套娃。。。。都是调用的同一个方法，可想而知，是一个递归。

那么定义一个函数，它的作用是从a中取球，取到满足条件输出组合。再定义一个index，表示我取得是哪一个球。之后，我们取球，如果要选，把a[index]置为1，参数curr表示已经取了多少个球，所以也需要+1，然后再去取下一个球。如此反复。

当然我们也可以不取这个球，不取这个球，就要把它置为0，但是需要index++，因为不取这个球，那还是需要去取下一个球，比如不取A，但是我们还是要去BC。

紧接着找到递归出口，也就是取完2个球，或者3个球都被取完了。得到之后，就把它打印出来。也就是调用show(a[])方法。

show方法:遍历i数组，如果a[i]==1，即我们取了，就把他输出。(char)('A'+i)+" "这也是个小细节。

代码

/*从5个小球中取出三个小球*/
public class 组合 {
    static int count;
    //很明显是一个组合问题,不用考虑排列，排列的话，就可以用全排列
    public static void main(String[] args) {
        int a[] = {0,0,0};
        method1(a,0,2,0);
        System.out.println(count);
    }

    /**
     * 作用: 从a中取球，取到2个球有哪几种组合
     *
     * @param a 数组a表示当前被选中的数
     * @param index 当前被选中的数的索引
     * @param sum  要选中多少个数
     * @param curr  当前已经选中了多少个数
     */
    private static void method1(int a[], int index, int sum, int curr) {
        if (curr == sum){
            show(a);
            count++;
            return;
        }
        //如果数组都选完了，就不能选了,之所以index == a.length，是因为最后一个也要被选
        if (index == a.length){
            return;
        }
        //当前位置要选，将这个位置改为1
        a[index] = 1;
        //判断下一个数是否要选
        method1(a,index+1,sum,curr+1);
        //当前这个位置不选，将这个位置改为0
        a[index] = 0;
        method1(a,index+1,sum,curr);

    }

    private static void show(int[] a) {
        for (int i =0; i < a.length;i++){
            if (a[i] == 1 ){
                System.out.print((char)('A'+i)+" ");//变成char与int相加为int，所以再把它变成char
            }
        }
        System.out.println();
    }
}