求组合的问题,跟求排列的问题类似,很容易的想到递归的实现方式。
在求一个字符串中所有字符的组合的时候,针对一个字符,有两种情况,假设在长度为n的字符串中选择长度为m的组合字符串,
第一是选择长度为n的字符串中的第一个字符,那么要在其余的长度n-1的字符串中选择m-1个字符
第二是不选择长度为n的字符串中的第一个字符,那么要在其余的长度n-1的字符串中选择m个字符
递归结束的条件就是,当m为0,即从字符串中不再选出字符的时候,这个时候已经找到了m个字符的组合,输出即可。还有一个条件是,当输入的字符串是串,自然是不能从中选出任何字符的。
package yuesef; import java.util.ArrayList; import java.util.List; public class TT { public static void main(String ss[]) { perm("123"); System.out.println(); } // 求字符串中所有字符的组合abc>a,b,c,ab,ac,bc,abc public static void perm(String s) { List<String> result = new ArrayList<String>(); for (int i = 1; i <= s.length(); i++) { perm(s, i, result); } } // 从字符串s中选择m个字符 public static void perm(String s, int m, List<String> result) { // 如果m==0,则递归结束。输出当前结果 if (m == 0) { for (int i = 0; i < result.size(); i++) { System.out.print(result.get(i)); } System.out.println(); return; } if (s.length() != 0) { // 选择当前元素 result.add(s.charAt(0) + ""); perm(s.substring(1, s.length()), m - 1, result); result.remove(result.size() - 1); // 不选当前元素 perm(s.substring(1, s.length()), m, result); } } }