华为机试ACM（字符组合问题）

今晚做了华为的机试，3道ACM题，最后一道是实现从M个不同字符中任取N个字符的所有组合。

eg: input:ABC 2

output:AB AC BC

第一个输入为字符串，第二个输入为组合的字符个数，当N=0或者N>M时，输出“ERROR”。

思路：可以用递归的算法解决，例如ABC中2个字符的所有组合，先选取第一个的A，那包含A的2个字符的所有组合就是从后面剩余的BC中取1个字符的所有组合，然后选取第二个的B，那包含B的2个字符的所有组合就是从后面剩余的C中取1个字符的组合，即只有C，到选取第三个的C时，后面已经没有字符了，不足以组成2个字符的组合。以此类推，将从M个不同字符中任取N个字符的所有组合递归成从M-1个不同字符任选N-1个字符的所有组合（包含“A”）加上从M-1个个不同字符任选N个字符的所有组合(不包含“A”)。

import java.util.*;

public class Main {

		public static void main(String args[]){

			        Scanner cin = new Scanner(System.in);

			        String str = cin.next();

			        int maxCount = cin.nextInt();

			        char[] chs = str.toCharArray();

			        if(maxCount==0 ||maxCount>str.length()){

			        	System.out.print("ERROR");

			        }

			        combination(chs, 0, 0, maxCount, "");

			    }

      /*

       * @param chs 输入的字符数组

       * @param index 选取的字符所在的数组索引值

       * @param count 已经选取字符的个数

       * @param maxCount 输入的要选取字符的个数

       * @param result 已经选取的字符组合

       *

       */

	   public static void combination(char[] chs, int index, int count, int maxCount, String result) {

		   if (count == maxCount) {

			   System.out.print(result+" ");

			   return;

		   }

		   for (int i = index; i < chs.length; ++i) {

			   combination(chs, i + 1, count + 1, maxCount, result + chs[i]);

		   }

	   }

}

巴特西

华为机试ACM（字符组合问题）

最新文章

热门文章