注：本文记录了代码编写及调试过程，想直接浏览正确答案的请移步文章结尾。

一、字符串的全排列问题

1. 下面是最初的代码（答案有错误-重复输出）

 import java.util.Scanner;

 public class Main {

     public static void main(String[] args) {

         Scanner sc = new Scanner(System.in);

         while (sc.hasNext()) {

             String str = sc.nextLine();

             char[] ch = str.toCharArray();

             //print(ch);

             permutation(ch);

         }

     }

     public static void permutation(char[] ch) {

         if (ch == null || ch.length < 1) {

             return;

         }else {

             permutation(ch, 0);

         }

     }

     public static void permutation(char[] ch, int begin) {

         char tmp ;

         if (begin == ch.length - 1) {

             print(ch);

             System.out.println();

             return;

         }else {

             for (int i = 0; i < ch.length; i++) {

                 tmp = ch[begin];

                 ch[begin] = ch[i];

                 ch[i] = tmp;

                 permutation(ch, begin + 1);

                 tmp = ch[begin];

                 ch[begin] = ch[i];

                 ch[i] = tmp;

             }

         }

     }

     public static void print(char[] ch) {

         for (int i = 0; i < ch.length; i++) {

             System.out.print(ch[i]);

         }

     }

 }

思想：固定、交换、递归。

举例：输入abc，第一次先固定第一个字符a，使用递归交换a后面的字符（这里递归指的是a后面的字符串也是先固定第一个字符，之后再交换其后的字符）。

错误：输入abc，输出结果bac abc acb abc bac bca bca cba cab

2. debug过程

看到输出答案中有重复，猜想可能是字符交换的循环写的有问题，找到循环，第一眼就看到一个错误，for循环的迭代变量i初始值设置为0，这样达不到“固定”的效果，改之。输出正确。

结果

输入：abc

输出：abc acb bac bca cba cab

3.正确代码

 import java.util.Scanner;

 public class Main {

     public static void main(String[] args) {

         Scanner sc = new Scanner(System.in);

         while (sc.hasNext()) {

             String str = sc.nextLine();

             char[] ch = str.toCharArray();

             permutation(ch);

         }

     }

     public static void permutation(char[] ch) {

         if (ch == null || ch.length < 1) {

             return;

         }else {

             permutation(ch, 0);

         }

     }

     public static void permutation(char[] ch, int begin) {

         char tmp ;

         if (begin == ch.length - 1) {

             print(ch);

             System.out.print(" ");

             return;

         }else {

             for (int i = begin; i < ch.length; i++) {

                 tmp = ch[begin];

                 ch[begin] = ch[i];

                 ch[i] = tmp;

                 permutation(ch, begin + 1);

                 tmp = ch[begin];

                 ch[begin] = ch[i];

                 ch[i] = tmp;

             }

         }

     }

     public static void print(char[] ch) {

         for (int i = 0; i < ch.length; i++) {

             System.out.print(ch[i]);

         }

     }

 }

二、字符串的组合问题

思想：分成两部分，（1）要打印的字符在第一部分，则在其后找其他（number-1）个字符。（2）要打印的字符不在第一部分，则在其后找其他（number）个字符

注：（1）这里用了递归的方法。（2） number表示每次打印共有几个字符。

正确代码

注：程序中使用了stack容器保存结果，大家可以使用其他更加熟悉的容器。

 import java.util.Scanner;

 import java.util.Stack;

 public class Main {

     public static void main(String[] agrs) {

         Scanner sc = new Scanner(System.in);

         while (sc.hasNext()) {

             String str = sc.nextLine();

             char[] ch = str.toCharArray();

             combine_str(ch);

         }

     }

     public static void combine_str(char[] ch) {

         if (ch == null || ch.length < 1) {

             return;

         }

         Stack<Character> stack = new Stack<Character>();

         for (int i = 1; i <= ch.length; i++) {

             combine_str(ch, 0, i, stack);

         }

     }

     public static void combine_str(char[] ch, int begin, int number, Stack<Character> stack) {

         if (number == 0) {

             System.out.print(stack.toString() + " ");

             return;

         }

         if (begin == ch.length ) {

             return;

         }

         stack.push(ch[begin]);

         combine_str(ch, begin + 1, number - 1, stack);

         stack.pop();

         combine_str(ch, begin + 1, number, stack);

     }

 }

结果

输入： abc

输出： [a] [b] [c] [a, b] [a, c] [b, c] [a, b, c]

巴特西

【算法与数据结构】Java实现字符串的全排列及组合