全排列问题

在各种算法竞赛，或者是笔试面试的过程中，全排列问题非常常见，列举一下一个经典的全排列问题，以遍后期巩固

剑指 Offer 38. 字符串的排列:

输入一个字符串，打印出该字符串中字符的所有排列。


​

示例:

输入：s = "abc"
输出：["abc","acb","bac","bca","cab","cba"]
​

这是一个典型的全排列问题，那么遇到全排列问题我们到底该如何处理呢？

1. 首先我们就想到了递归
2. 然后我们需要一个辅助数组
3. 然后我们还用到了回溯算法

我们可以用一个数组 boolean used [ ] 来表示当前位置的字符是否使用过，如果使用过的话那么我们进行下一位，最后再还原 为初始状态。贴一下代码，下面的代码也是一个模板！

import java.util.*;

public class lk {
	static Set<String> set = new HashSet<>(); //hash去重

	public static void main(String[] args) {
		String str = "ABCD";
		boolean[] used = new boolean[str.length()];
		dfs(str, used, "");
		for (String strs : set) {
			System.out.println(strs);
		}
	}

	private static void dfs(String str, boolean[] used, String string) {
		// TODO Auto-generated method stub
		if (string.length() == str.length()) { //终止条件
			set.add(string);
			return;
		}
		for (int i = 0; i < str.length(); i++) {
			if (used[i]) {
				continue;
			} else {
				used[i] = true;
				dfs(str, used, string+str.charAt(i) );
				used[i] = false; //回溯
			}
		}

	}
}

​