回溯法：生成一个字符串的所有排列组合
问题：字符串abcd怎样获取abcd、acbd、acdb、adbc、adcb、bacd、bcad、bdac、bdca、cabd、cdba、cadb、cbda等，所有排列。
使用回溯法来生成一个字符串的所有排列
import java.util.ArrayList;
import java.util.List;public class Permutations {public static void main(String[] args) {// 目标字符串String str = "abcd";// 调用permute方法获取所有排列，并打印结果List<String> permutations = permute(str);for (String permutation : permutations) {System.out.println(permutation);}}/*** 生成字符串的所有排列。* @param str 输入的字符串* @return 包含所有排列的列表*/private static List<String> permute(String str) {List<String> result = new ArrayList<>();// 如果字符串为空或长度为0，则返回空列表if (str == null || str.length() == 0) {return result;}// 使用字符数组，并从第一个字符开始进行排列char[] chars = str.toCharArray();permuteHelper(chars, 0, result);return result;}/*** 递归辅助方法，用于生成排列。* @param chars 字符数组，用于交换字符以生成排列* @param index 当前处理字符的位置索引* @param result 存储所有排列结果的列表*/private static void permuteHelper(char[] chars, int index, List<String> result) {// 如果已经处理到最后一个字符，将当前排列加入结果列表if (index == chars.length - 1) {result.add(new String(chars));} else {// 对于每个未处理的字符，都尝试将其放在当前位置for (int i = index; i < chars.length; i++) {// 交换当前字符与待处理字符swap(chars, index, i);// 递归处理下一个字符位置permuteHelper(chars, index + 1, result);// 回溯：恢复交换前的状态，以便尝试下一个字符swap(chars, index, i);}}}/*** 交换字符数组中的两个元素。* @param array 字符数组* @param a 第一个元素的索引* @param b 第二个元素的索引*/private static void swap(char[] array, int a, int b) {char temp = array[a];array[a] = array[b];array[b] = temp;}
}