全排列

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner reader = new Scanner(System.in);
        char[] input = reader.next().toCharArray();
        Arrays.sort(input);
        ArrayList<Character> path = new ArrayList<>();
        boolean[] visited = new boolean[input.length];
        helper(input, path, visited);
        System.out.println();
    }
    public static void helper(char[] str, ArrayList<Character> path, boolean[] visited) {
        if (path.size() == str.length) {
            for (char c: path) {
                System.out.print(c);
            }
            System.out.println();
            return;
        }
        for (int i = 0; i < str.length; ++i) {
            if (visited[i])
                continue;
            path.add(str[i]);
            visited[i] = true;
            helper(str, path, visited);
            path.remove(path.size()-1);
            visited[i] = false;
        }
    }
}

//用dfs写的，主要是排序和去重吧
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;
public class Main{

    public static void main(String[] args){
        testFullArrMent();
    }

    static boolean[] flag;
    static List<String> list = new ArrayList<String>();
    public static void testFullArrMent(){
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        char[] ch = s.toCharArray();
        char[] c = new char[ch.length];
        flag  = new boolean[ch.length];
        dfs(ch,c,0);
        Collections.sort(list);
        for(String str:list){
            System.out.println(str);
        }
        System.out.println();
    }


    private static void dfs(char[] ch, char[] c, int k) {
        // TODO Auto-generated method stub
        if(k==ch.length){
            String s = String.valueOf(c);
            if(!list.contains(s)){
                list.add(s);
            }

        }
        for(int i=0;i<ch.length;i++){
            if(!flag[i]){
                flag[i]=true;
                c[k]=ch[i];
                dfs(ch,c,k+1);
                flag[i]=false;
            }
        }
    }

}

/*
 * 思路 深搜字典排序
 * 尽可能的搜索每一条路径，一旦搜索到某条路径的尽头时，则回溯到该路径的上
 * 一节点，若上一节点有未搜过的边，则沿着这条边继续搜索，如此反复知道所有
 * 节点都被搜索过
 */
import java.util.*;

public class Main {
    static int[] used = new int[7];//标记某个字符是否被使用过
    static char[] a = new char[7];
    static int total;
    static int N;

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner input = new Scanner(System.in);

        String str = input.nextLine();
        String[] tokens = str.split(" ");

        for (int i = 0; i < tokens.length; i++) {
            char[] arr = tokens[i].toCharArray();
            Arrays.sort(arr);
            N = arr.length;
            dfs(0, arr);
        }
    }

    static void dfs(int i, char[] arr) {
        if (i >= N) {//递归结束，打印结果
            print();
        }
        else
            for (int k = 0; k < N; k++) {
                if (used[k] == 0) {
                    used[k] = 1;//已使用过的标记
                    a[i] = arr[k];//赋值
                    dfs(i + 1, arr);
                    used[k] = 0;//还原为未使用
                }
            }
    }

    static void print() {
        for (int k = 0; k < N; k++) {
            System.out.print(a[k]);
        }
        System.out.println();
    }
}

import java.util.Arrays;
import java.util.Scanner;
/*
 * 思路:
 * 当我试着分解问题时,发现,n个数(a1,...,an)的全排列可以分解为a1拼接(n-1)个数全排列.直到1个数的全排列.此时能够确定某一个排列.
 * 自然会去尝试一下递归处理
 * # 那么思考递归变量是哪些呢?
 * 1. 参与全排列的元素在变,用char[]数组变量表示
 * 2. 因为要打印完整的全排列,每次父问题分为前后两半之后,前半边字符串需要传递进来和后半边字符串进行拼接,然后打印.
 * 
 * # 递归的边界条件是什么呢?
 * 1. 我们能直观感受到只有一个数时,问题不能再分解,并且可以拼接,打印字符串了.
 * 2. 但是,我们可能要用递归变量来具体化边界情况. recursive(前半边字符串=不怎么好描述...,char[] = 1个元素(这个1很好确定),);
 * 
 * # 打印的顺序满足字典序吗?
 * 卧槽,是满足的.
 */
public class Main_Sure {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		while (scanner.hasNextLine()) {
			char[] input = scanner.nextLine().toCharArray();
			Arrays.sort(input);//有坑,存在"dbc"这种顺序打乱的test case,所以排个序.
			fullPermutation("", input);
			System.out.println();
		}
	}

	public static void fullPermutation(String pre, char[] inputs) {
		if (inputs.length == 1) {
			System.out.println(pre.toString() + inputs[0]);
			return;
		}
		//分类计数原理计算全排列的排列个数: 每个字符都要做一次开头. 这样分类完备,无重复.
		//inputs[i]:某全排列开头的字符.
		for (int i = 0; i < inputs.length; i++) {
			char[] rest = new char[inputs.length - 1];
			int index = 0;
			for (int j = 0; j < inputs.length; j++) {
				if (i != j) {
					rest[index++] = inputs[j];
				}
			}
			fullPermutation(pre +""+inputs[i], rest);
		}
	}
}