package String_process;

import java.util.Deque;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;
/**
 * @author dx
 * @version 1.0
 * @date 2022年5月11日 17:06
 * @description: 输入一个字符串,打印出该字符串中字符的所有排列
 * 回溯:https://zhuanlan.zhihu.com/p/93530380
 */
public class Permutation {
 public static void main(String[] args) {
 Scanner sr = new Scanner(System.in);
 String s = sr.nextLine();
 List<List<Character>> res = new LinkedList<>();
 System.out.println(new Permutation_solution().permutation(s));
 }
}

class Permutation_solution{
 List<List<Character>> res = new LinkedList<>();
 //输入字符串
 public List<List<Character>> permutation(String s){
 char x[] = s.toCharArray();

 //记录路径
 LinkedList<Character> track = new LinkedList<>();
 backtrace(x,track);
 return res;

 }
 public void backtrace(char []s,LinkedList<Character> track){
 //触发结束条件:当路径长度等于全排列的长度,则添加到返回值里面
 if(track.size() == s.length){
 res.add(new LinkedList<>(track));
 return;
 }
 for(int i = 0; i < s.length; i++){
 //排除不合法的选择
 if(track.contains(s[i])){
 continue;
 }
 //做选择:加到track中
 track.add(s[i]);
 //进入到下一层决策树
 backtrace(s,track);
 //取消选择:当下一层一到了最底层,则开始取消其(最底层)"当前节点"的选择
 track.removeLast();
 }
 }
 //以两个节点为例:String s = ab
 /*
 第一层 ----》 第二层
 1、for i =1 1、for 1 continue,for 2:
 2、trace add(a) 2、trace add(ab)

 3、backtrace() ---------------> track.size() == s.length
 /
 /
 3、backtrace() ------> 进入第二层 4、 ----------------- trace.removeLast
 |
 |
 |
 trace:a (b删除),并且for循环结束
 /
 /
 /
 4、trace.removeLast()
 |
 |
 |
 trace :空,进入下一个循环
 5、for i =2
 6、 trace add(b)





 ====》第二层
 1、for i= 1
 2、trace add(ba)

 3、backtrace() ------>trace.size() == s.length
 /
 /
 /
 7、backtrace() ------>进入第二层 4、-------------------------------trace.removeLast
 |
 |
 |
 trace: b(a删除),并且for进入i = 2 continue,结束循环
 /
 /
 /
 8、trace.removeLast()
 |
 |
 |
 trace:空,结束程序

 */




}