示例2:
输入：S = "ab" 输出：["ab", "ba"] 答案 class Solution { StringBuilder sb = new StringBuilder(); List<String> list = new ArrayList<>(); boolean[] used; public String[] permutation(String S) { used = new boolean[S.length()]; f(S, 0); return list.toArray(new String[list.size()]); } public void f(String S, int depth) { if (depth >= S.length()) { list.add(sb.toString()); } for (int i = 0; i < S.length(); i++) { if (!used[i]) { sb.append(S.charAt(i)); used[i] = true; f(S, depth + 1); sb.delete(sb.length() - 1, sb.length()); used[i] = false; } } } } 面试题 08.08. 有重复字符串的排列组合有重复字符串的排列组合。编写一种方法，计算某字符串的所有排列组合。
示例1:
输入：S = "qqe" 输出：["eqq","qeq","qqe"]示例2:
输入：S = "ab" 输出：["ab", "ba"] 答案 class Solution { StringBuilder sb = new StringBuilder(); Set<String> list = new HashSet<>(); boolean[] used; public String[] permutation(String S) { used = new boolean[S.length()]; f(S, 0); return list.toArray(new String[list.size()]); } public void f(String S, int depth) { if (depth >= S.length()) { list.add(sb.toString()); } for (int i = 0; i < S.length(); i++) { if (!used[i]) { sb.append(S.charAt(i)); used[i] = true; f(S, depth + 1); sb.delete(sb.length() - 1, sb.length()); used[i] = false; } } } } 方法二：交换省去标志数组即 以index为界限，index左边为排好序的元素，index右边为未排好序的元素，我们需要从右边挑选出元素放入左边。
class Solution { public String[] permutation(String s) { Set<String> res = new HashSet<>(); char[] C = s.toCharArray(); backtrack(0, C, res); String[] ans = new String[res.size()]; int i = 0; for (String str : res) ans[i++] = str; return ans; } private void backtrack(int index, char[] S, Set<String> res) { if(index == S.length - 1) { res.add(String.valueOf(S)); return; } for(int i = index; i < S.length; i++) { swap(index, i, S); backtrack(index + 1, S, res); swap(index, i, S); } } private void swap(int i, int j,char[] C) { char temp = C[i]; C[i] = C[j]; C[j] = temp; } } 面试题 08.10. 颜色填充编写函数，实现许多图片编辑软件都支持的「颜色填充」功能。
待填充的图像用二维数组 image 表示，元素为初始颜色值。初始坐标点的行坐标为 sr 列坐标为 sc。需要填充的新颜色为 newColor 。
「周围区域」是指颜色相同且在上、下、左、右四个方向上存在相连情况的若干元素。
请用新颜色填充初始坐标点的周围区域，并返回填充后的图像。
示例：
输入： image = [[1,1,1],[1,1,0],[1,0,1]] sr = 1, sc = 1, newColor = 2 输出：[[2,2,2],[2,2,0],[2,0,1]] 解释: 初始坐标点位于图像的正中间，坐标 (sr,sc)=(1,1) 。 初始坐标点周围区域上所有符合条件的像素点的颜色都被更改成 2 。 注意，右下角的像素没有更改为 2 ，因为它不属于初始坐标点的周围区域。 答案 class Solution { int color; public int[][] floodFill(int[][] image, int sr, int sc, int newColor) { color = image[sr][sc]; return f(image, sr, sc, newColor); } public int[][] f(int[][] image, int sr, int sc, int newColor) { if (sr < 0 || sr >= image.length || sc < 0 || sc >= image[0].length || image[sr][sc] != color || image[sr][sc] == newColor) { return image; } image[sr][sc] = newColor; // 上 image = f(image, sr - 1, sc, newColor); // 左 image = f(image, sr, sc - 1, newColor); // 下 image = f(image, sr + 1, sc, newColor); // 右 image = f(image, sr, sc + 1, newColor); return image; } } 面试题 08.09. 括号括号。设计一种算法，打印n对括号的所有合法的（例如，开闭一一对应）组合。
说明：解集不能包含重复的子集。
例如，给出 n = 3，生成结果为：
[ "((()))", "(()())", "(())()", "()(())", "()()()" ] 答案我们第一眼就可以看出这是一个回溯法的运用，那么我们需要明确函数功能，确定它的参数。
我们的节点状态有两种表达方式：
深度，括号匹配数：深度为括号总数，括号匹配数遇到左括号+1，遇到右括号-1，直到0。
左括号数，右括号数：左右括号数。
这题就是说明递归出口不一定唯一的最好例子，因为我们有多个状态参数。
深度，括号匹配数 class Solution { int n; List<String> res = new ArrayList<>(); StringBuilder sb = new StringBuilder(); public List<String> generateParenthesis(int n) { this.n = n; f(0, 0); return res; } // depth为递归深度，count为左右括号配比，左括号+1，右括号-1 public void f(int depth, int count) { if (depth > 2 * n || count < 0) { return; } if (depth >= 2 * n && count == 0) { res.add(new String(sb)); return; } sb.append("("); f(depth + 1, count + 1); sb.delete(sb.length() - 1, sb.length()); sb.append(")"); f(depth + 1, count - 1); sb.delete(sb.length() - 1, sb.length()); } } 左括号数，右括号数