字符串的组合（C（m,n））

题目：有A,B,C,D,E 5个字母，从其中任选3个，要求列出所有可能的组合

?

大家一定还记得高中的时候学过的组合C（m,n）算法吧。。那么我们就用这个算法来做这道题吧。

?

其实做出这道题有俩种方法，一种是递归的。比较容易一点。另外一种是非递归的。

?

递归的代码如下：

?

/* * 主要是利用递归来来实现。主要思想是把一个字符串分为俩段来处理，首先取出第一个字符串，然后用后面的字符来与它进行拼凑。 */import java.util.Scanner;public class Zuhe {private static String str = "ABCDE";// 字符串private static int n = 3;// 选择的个数private static int count = 0;//组合的个数public static void main(String[] args) {new Zuhe();}Zuhe() {Scanner input = new Scanner(System.in);System.out.println("请输入要选择的个数（要少于" + str.length() + "个）");n = Integer.parseInt(input.nextLine());find("", 0);System.out.println("共有"+count+"种组合");}/* *第一个参数是代表第一个字符，第二个参数代表开始寻找点的位置 */public static void find(String s, int i) {// 保存上一次的字符串String temp = s;//判断是否符合要求if (s.length() == n) {count++;System.out.print(s + " ");if (count % 10 == 0)System.out.println();return;}//从寻找点开始循环，for (int k =i; k < str.length(); k++) {s = temp;s += str.charAt(k);find(s, k+1);}}}

?

?非递归的代码如下：

/* * 采用了图的广度优先算法。也可以说利用队列来实现。先进先出。首先取出第一个字母。然后入队、。 * 开始循环，出队。循环的结束条件的只要队列还有元素就就循环没有结束。进入循环之后，先判断元素是否符合 * 要求，如果符合就输出。如果不符合，就给它追加一个字母，开始点是由它的最后一个字符来决定。 * 比如说：是A就从0开始，是B就从1开始。（这里是难点。）一直找到字符串的末尾。找完之后就 * 去除取出来的这个元素。以此类推。。。 */import java.util.ArrayList;import java.util.Scanner;public class Zuhe {public static void main(String[] args) {String str = "ABCDE";// 字符串int n = 2;// 选择的个数int count = 0;// 组合的总数Scanner input = new Scanner(System.in);System.out.println("请输入要选择的个数（要少于" + str.length() + "个）");n = Integer.parseInt(input.nextLine());ArrayList<String> arr = new ArrayList<String>();//模拟队列for (int k = 0; k < str.length(); k++) {//取出首节点String s = str.charAt(k) + "";//入队arr.add(s);//开始循环while (arr.size() > 0) {//出队String ss = arr.get(0);//判断是否符合要求if (ss.length() == n) {System.out.print(ss + "  ");count++;if (count % 10 == 0)System.out.println();}//追加字符。for (int i = str.indexOf(ss.charAt(ss.length() - 1))+1; i < str.length(); i++) { if (ss.length() < n) {String m = ss + str.charAt(i);arr.add(m);}}//去除取出来的节点。arr.remove(0);}}System.out.println("共有" + count + "种组合");}}

?结果的输出效果：

请输入要选择的个数（要少于5个）
3
ABC ABD ABE ACD ACE ADE BCD BCE BDE CDE
共有10种组合