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

你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。

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

限制：

• 1 <= s 的长度 <= 8

分析：

方法：回溯+DFS

这道题要求返回所有的排列，而排列最容易让人想到的就是交换顺序，拿 "abc" 举例：

• 先固定 a 不动，交换 b 和 c，这样就得到了两个答案 abc 和 acb
• a 和 b 交换，固定 b 不动，变换 a 和 c，这样得到答案 bac 和 bca
• a 和 c 交换，固定 c 不动，交换 a 和 b，这样得到答案 cba 和 cab

三个以上字母也是如此，固定首字母（相当于自己和自己交换），对后面字母进行一样的操作，然后交换首字母，依次循环就可以得到所有答案。我们可以用深度遍历（DFS）来实现，每遍历一层就将该层的字符与后面的字符交换，为避免重复交换，可以定义个哈希集合还存储交换过的字符。

时间复杂度：O(n*n!) 
空间复杂度：O(n^2)

class Solution {//定义字符数组，存储字符串的所有字符char[] cs;//定义哈希集合存储交换后的结果List<String> list = new ArrayList<>();public String[] permutation(String s) {cs = s.toCharArray();//开始遍历dfs(0);//结果数组return list.toArray(new String[0]);}public void dfs(int n){//遍历到最后一个字符串，添加结果到集合if(n == cs.length-1){list.add(String.valueOf(cs));return;}//记录交换过的字符，防止重复交换HashSet<Character> set = new HashSet<>();//遍历，进行交换for(int i = n; i < cs.length; ++i){if(!set.contains(cs[i])){//进行交换swap(n, i);//深度遍历dfs(n+1);//交换回来swap(n, i);//记录字符set.add(cs[i]);}}}//交换方法public void swap(int i, int j){char c = cs[i];cs[i] = cs[j];cs[j] = c;}
}

题目来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof