秒杀排列组合（下）————组合篇
首先为什么要写排列组合？因为排列组合在数学中占有重要的地位，其与概率论也有密切关系；并且排列组合问题在求职的笔试，面试出现的概率特别高，而我在网上又没有搜到比较全面题型的文章；同时，我觉得编写排列组合程序对学习递归也是很有帮助的；当然，最重要的原因是排列组合本身就很有趣！所以就总结下排列组合的各种问法，分两篇写：上篇写排列，下篇写组合。
组合篇
排列篇地址：http://blog.csdn.net/nash_/article/details/8351611
首先从各大IT公司的题中总结出排列组合的对象都是整形数组或字符数组，而且绝大部分组合问题都是无重复数字或者字符的；所以组合问题可以按输入数据分为两大类：输入数据有重复和无重复，又可以按输出数据分为两大类：输出数据有重复和无重复。
由于侧重点在输入数据无重复，所以先看输入数据无重复类型：
如a={1,2,3}。当n=2时候的所有组合数为12，13，23
算法思想：按递增顺序输出，如12,13,14,15.....23.24.25........34,35.............用一个变量begin遍历的第一个数
代码清单：
public class ZuHe {public void combine(int m, int n) {if(m < 1 || n < 1)return;if(n > m)//如果n>m,把n>m的数去掉n = m;boolean[] b = new boolean[n+1];//保存是否装包getCombination(m, n, b);}public void getCombination(int m, int n, boolean[] b){if(m < 1 || n < 1)//递归出口return;if(m == n){//输出组合b[n] = true;for(int i = 1; i < b.length; i++){if(b[i] == true)System.out.print(i + " ");}System.out.println();b[n] = false;}b[n] = true;//装包getCombination(m-n, n-1, b);b[n] = false;//不装包getCombination(m, n-1, b);}public static void main(String[] args){ZuHe robot = new ZuHe();int[] a = {1,2,3,4};int n = 3;robot.combine(10,12);}}如m =3,n=2 输出111，12
算法思想：由于组合元素个数未知，所以改用集合存储，使集合内元素有序为了去重，当m=0时候输出结果。
代码清单：
public class ZuHe {public void combine(int m, int n) {if(m < 1 || n < 1)return;int[] b = new int[n];getCombination(m, n, b, 0, 1);}private void getCombination(int m, int n,int b[], int index,int begin) {// TODO Auto-generated method stubif(n == 0 && m == 0){for(int i = 0; i < b.length; i++)System.out.print(b[i] + " ");System.out.println();}if(n == 0)return;for(int i = begin; i <= m; i++){b[index] = i;getCombination(m-i,n-1,b ,index+1,i);}}public static void main(String[] args){ZuHe robot = new ZuHe();robot.combine(5,3);}}如m=6，n=3 输出123
算法思想：按递增序列递归求解，如果 n==0 && m==0 输出结果，如果n==0,m!=0,返回，将递归调用设置成i+1
代码清单：
public class ZuHe {public void combine(int m, int n) {if(m < 1 || n < 1)return;int[] b = new int[n];getCombination(m, n, b, 0, 1);}private void getCombination(int m, int n,int b[], int index,int begin) {// TODO Auto-generated method stubif(n == 0 && m == 0){for(int i = 0; i < b.length; i++)System.out.print(b[i] + " ");System.out.println();}if(n == 0)return;for(int i = begin; i <= m; i++){b[index] = i;getCombination(m-i,n-1,b ,index+1,i+1);}}public static void main(String[] args){ZuHe robot = new ZuHe();robot.combine(5,3);}}如m=3 输出111，12，3
算法思想（与算法4相同）：由于组合元素个数未知，所以改用集合存储，使集合内元素有序为了去重，当m=0时候输出结果
代码清单：
public class ZuHe {public void combine(int[] a) {if(null == a || a.length == 0)return;int[] b = new int[a.length];getCombination(a, 0, b, 0);}private void getCombination(int[] a, int begin, int b[], int index) {if(index >= a.length)return;for(int i = begin; i < a.length; i++){b[index] = a[i];printArray(b,index);getCombination(a, i+1, b, index+1);}}private void printArray(int[] b, int index) {for(int i = 0; i < index+1; i++){System.out.print(b[i] + " ");}System.out.println();}public static void main(String[] args){ZuHe robot = new ZuHe();int[] a = {1,2,3};robot.combine(a);}}如a={1,2}输出1，11，12，2，22
算法思想：我们把输出顺序重新排列：1，12，123，13，2，23，3可以看出规律以1开头加上以非1开头的所有组合就构成了以1开头的所有组合，2，3同理，用一个参数index控制输出范围，去掉begin参数，保持序列递增有序。
代码清单：
public class ZuHe {public void combine(int[] a) {if(null == a || a.length == 0)return;int[] b = new int[a.length];getCombination(a, b, 0);}private void getCombination(int[] a, int b[], int index) {if(index >= a.length)return;for(int i = 0; i < a.length; i++){if(index == 0 || a[i] >= b[index-1]){b[index] = a[i];printArray(b,index);getCombination(a, b, index+1);}}}private void printArray(int[] b, int index) {for(int i = 0; i < index+1; i++){System.out.print(b[i] + " ");}System.out.println();}public static void main(String[] args){ZuHe robot = new ZuHe();int[] a = {1,2,3};robot.combine(a);}}这类如a={1,3,2,3}，这种问题相对较少，博主可以没有什么特别好的想法，只想到了两种通用的思路：
思路一：每次添加一个序列时，判断此序列是否已添加过。
思路二：添加所有的序列，最后去重。
两种思路解法差不多，但由于判断的是一个序列存不存在，所以不能直接用Hash，博主按思路一写了一题的解法供参考：
题目：输出数组a的所有数的所有组合如a={1,2,2}输出111，112，122，222
算法思想：在判断序列是否已添加之前，排序该序列，再验证；如果不存在，拷贝该序列添加到集合中。
代码清单：
import java.util.ArrayList;import java.util.Collections;import java.util.Comparator;import java.util.List;public class ZuHe {/*保存序列集合*/ArrayList<List<Integer>> _arr = new ArrayList<List<Integer>>();public void combine(int[] a) {if(null == a || a.length == 0)return;List<Integer> b = new ArrayList<Integer>();//序列存储空间getCombination(a,b);printArr();//输出所有组合}public void getCombination(int[] a, List<Integer> b){if(a.length == b.size()){/*自定义按List中升序排序*/Collections.sort(b, new Comparator() {public int compare(Object o1, Object o2) {return (Integer)o1 - (Integer)o2;} });if(!haveArray(b)){//如果序列b不存在/*拷贝一个序列b*/List<Integer> new_list = new ArrayList<Integer>();for(int i = 0; i < b.size(); i++){new_list.add(b.get(i));}_arr.add(new_list);//加入集合中}return;}for(int i = 0; i < a.length; i++){Integer num = a[i];b.add(num);getCombination(a, b);b.remove(num);}}private boolean haveArray(List<Integer> b) {for(int i = 0; i < _arr.size(); i++){List<Integer> temp = _arr.get(i);int j;for(j = 0; j < temp.size(); j++){if(temp.get(j) != b.get(j))break;}if(j >= temp.size())return true;}return false;}public void printArr(){for(int i = 0; i < _arr.size(); i++){List<Integer> temp = _arr.get(i);for(int j = 0; j < temp.size(); j++)System.out.print(temp.get(j) + " ");System.out.println();}}public static void main(String[] args){ZuHe robot = new ZuHe();int[] a = {1,2,2};robot.combine(a);}}以上组合问题如果您有好的建议或者有其他的组合问题，请您留言，谢谢!
==================================================================================================
作者：nash_ 欢迎转载，与人分享是进步的源泉！
转载请保留原文地址：http://blog.csdn.net/nash_/article/details/8315418
===================================================================================================