import java.util.ArrayList;
import java.util.*;
public class Solution {
    private String s = null;
    private ArrayList<String> res=new ArrayList<>();
    private boolean visit[]=null;
    private void backtracking(StringBuilder stringBuilder){
        if(stringBuilder.length()==s.length()){
            res.add(stringBuilder.toString());
            return;
        }

        for(int i=0;i<s.length();i++){
            if(i!=0&&s.charAt(i)==s.charAt(i-1)&&!visit[i-1]){
                continue;
            }
            if(visit[i])
                continue;

            visit[i]=true;
            stringBuilder.append(s.charAt(i));
            backtracking(stringBuilder);
            stringBuilder.deleteCharAt(stringBuilder.length()-1);
            visit[i]=false;
        }
    }
    public ArrayList<String> Permutation(String str) {
        s=str;
        if(str==null||str.length()==0){
            return res;
        }
        visit=new boolean[str.length()];
        Arrays.fill(visit,false);
        backtracking(new StringBuilder());
        System.out.println(res.toString());
        return res;
    }

    public static void main(String[] args) {
        Solution solution=new Solution();
        ArrayList<String> res = solution.Permutation("abc");
    }