字符串的排列（全排列）——Java、回溯法
题目描述 输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。 输入描述:
输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。
Solution：
文章图片
【字符串的排列（全排列）——Java、回溯法】从这张图中，我们可以看出来，找全排列类似于深度优先遍历，深度优先最关键的就是要记住上一个状态，而所谓回溯就是要回到上一没有操作过的状态，再去考虑别的情况。
例如上面这个图，我们的想法是每次都把一个数固定在前面，让后面的数递归地进行全排列，这样每个数都固定过以后就能找出所有排列。关键的地方在于，我们把每个数固定在前面并让后面的进行全排列完毕以后，要恢复原来的状态，也就需要交换回来。
具体的代码如下：
import java.util.*;
public class Solution {
public ArrayList Permutation(String str) {
ArrayList ans=new ArrayList<>();
//所有排列的可能都在这里
if(str!=null||str.length()>0){
help(0,str.toCharArray(),ans);
Collections.sort(ans);
}return ans;
}
public static void help(int i,char[] cha,ArrayList ans){
if(i==cha.length-1){
String val = String.valueOf(cha);
if(!ans.contains(val)){
ans.add(val);
}
}else{
for(int j=i;
j推荐阅读
- 热闹中的孤独
- JAVA（抽象类与接口的区别&重载与重写&内存泄漏）
- 放屁有这三个特征的，请注意啦！这说明你的身体毒素太多
- 一个人的旅行，三亚
- 布丽吉特，人生绝对的赢家
- 慢慢的美丽
- 尽力
- 一个小故事，我的思考。
- 家乡的那条小河
- 《真与假的困惑》???|《真与假的困惑》??? ——致良知是一种伟大的力量