组合算法Java实现

import java.util.Arrays;
/**
 * @author Freedom
 * 
 * 组合算法java实现
 * 方法：DFS
 * 思路：
 * 给定一个数组input，长度为N，现要从中选取r个元素,记其在num中下标为a1，a2.....ar
 * 1.选取第一个元素num[a1],则下一个元素的可选下标范围为[a1+1,N]
 * 2.同理，第二个元素num[a2]的下一个元素的可选下标范围为[a2+1,N]
 * 3.第三到第r个元素的选取与1，2点相同
 * 简而言之，组合是无序的，我们可以依次选取下标递增的元素构成组合项来不重复地输出所有组合；
 * 如：从{1，5，3，4}中选取两个元素，选取分析过程如下
 * {1,5} 在{1,5,3,4}中对应下标{0,1}
 * {1,3} 对应下标{0,2}
 * {1,4} 对应下标{0,3}
 * {5,3} 对应下标{1,2}
 * {5,4} 对应下标{1,3}
 * {3,4} 对应下标{2,3}
 * 可见所有组合项对应下标都是有序的
 *
 */
public class Combination {
    public static void dfs(int[] input
            ,int[] output,int index,int start){
        if(index==output.length)//产生一个组合序列
            System.out.println(Arrays.toString(output));
        else{
            for(int j=start;j<input.length;j++){
                output[index]=input[j];//记录选取的元素
                dfs(input,output,index+1,j+1);//选取下一个元素，可选下标区间为[j+1,input.length]
            }
        }
    }
    public static void main(String[] args){
        int[] input={1,2,3,4,5,6,7,8,9};
        int N=5;//组合长度
        int[] output=new int[N];
        dfs(input,output,0,0);
    }
}