总结
解决一个回溯问题，实际上就是一个决策树的遍历过程。你只需要思考 3 个问题：
1、路径：也就是已经做出的选择。
2、选择列表：也就是你当前可以做的选择。
3、结束条件：也就是到达决策树底层，无法再做选择的条件。
代码方面，回溯算法的框架：
result = []
def backtrack(路径, 选择列表):
if 满足结束条件:
result.add(路径)
return
for 选择 in 选择列表:
做选择
backtrack(路径, 选择列表)
撤销选择
全排列
给定一个 没有重复 数字的序列，返回其所有可能的全排列。
示例:
输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
回溯算法1：
路径：ArrayList<Integer> per，包含所有整数（不重复）的集合就是一条路径；
选择列表：nums和tags决定，所有未选择过的整数，都可以选择；
结束条件：per中的整数个数达到最大；
第一种算法的缺点为需要额外的tags来标识nums中的整数是否已经被选择过，第二种则不需要。时间负责度为。
public static List<List<Integer>> permute2(int[] nums) {
List<List<Integer>> pers = new ArrayList<>();
ArrayList<Integer> per = new ArrayList<>();
boolean[] tags = new boolean[nums.length];
backtrack2(pers, per, nums, tags);
return pers;
}
public static void backtrack2(List<List<Integer>> pers, ArrayList<Integer> per, int[] nums, boolean[] tags) {
if (per.size() == nums.length) {
pers.add(new ArrayList<>(per));
return;
}
for (int i = 0; i < nums.length; i++) {
if(!tags[i]){
per.add(nums[i]);
tags[i] = true;
backtrack2(pers, per, nums, tags);
per.remove(per.size()-1);
tags[i] = false;
}
}
}
回溯算法2：
将这个问题可以看作有 n 个的空格，我们需要从左往右依此填入题目给定的 n 个数，每个数只能使用一次。为了在选择下一个填入的数时不重复，我们需要将已经填过的数放在数组的左边，未填的数放在数组的右边。
具体来说，假设我们已经填到第 pos 个位置，那么nums[] 数组中 [0, pos−1] 是已填过的数的集合，[pos , n−1] 是待填的数的集合。我们肯定是尝试用 [pos, n−1] 里的数去填第 pos 个数，假设待填的数的下标为 i ，那么填完以后我们将第 i 个数和第 pos 个数交换，即能使得在填第 pos 个数的时候 nums[] 数组的[0,pos ] 部分为已填过的数，[pos +1,n−1] 为待填的数，回溯的时候交换回来即能完成撤销操作。
public class Solution {
private List<List<Integer>> ans;
private int[] nums;
public List<List<Integer>> permuteUnique(int[] nums) {
this.ans = new ArrayList<>();
this.nums = nums;
List<Integer> path = new ArrayList<>();
for (int num : nums) {
path.add(num);
}
backtrack(path, 0);
return ans;
}
public void backtrack(List<Integer> path, int pos) {
if (pos == nums.length - 1) {
ans.add(new ArrayList<>(path));
return;
}
for (int i = pos; i < nums.length; i++) {
Collections.swap(path, i, pos);
backtrack(path, pos + 1);
Collections.swap(path, i, pos);
}
}
}
全排列 II
为了去重，需要先排序；当相邻两个数相同，且前一个数刚刚被撤销（即visit=false），这种情况下会导致重复的排列，需要剪枝。
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> ans = new ArrayList<>();
if(nums.length == 0){
return ans;
}
// 排序是去重的前提
Arrays.sort(nums);
backtrace(ans, new ArrayList<>(nums.length), nums, new boolean[nums.length]);
return ans;
}
public void backtrace(List<List<Integer>> ans, List<Integer> path, int[] nums, boolean[] visit) {
if (path.size() == nums.length) {
ans.add(new ArrayList<>(path));
return;
}
for (int i = 0; i < nums.length; i++) {
if (i > 0 && nums[i] == nums[i - 1] && !visit[i - 1]) {
continue;
}
if (!visit[i]) {
visit[i] = true;
path.add(nums[i]);
backtrace(ans, path, nums, visit);
visit[i] = false;
path.remove(path.size() - 1);
}
}
}
交换去重
交换去重不需要提前排序，也不需要额外的visit数组，所以推荐使用此种方式进行全排列问题的求解。
public class Solution {
private List<List<Integer>> ans;
private int[] nums;
public List<List<Integer>> permuteUnique(int[] nums) {
this.ans = new ArrayList<>();
this.nums = nums;
List<Integer> path = new ArrayList<>();
for (int num : nums) {
path.add(num);
}
backtrack(path, 0);
return ans;
}
public void backtrack(List<Integer> path, int pos) {
if (pos == nums.length - 1) {
ans.add(new ArrayList<>(path));
return;
}
Set<Integer> set = new HashSet<>();
for (int i = pos; i < nums.length; i++) {
// 去重，在给pos位置赋值时，如果前面已经有过相同的数被赋值给pos，那么就过滤
if(set.contains(path.get(i))){
continue;
}
set.add(path.get(i));
Collections.swap(path, i, pos);
backtrack(path, pos + 1);
Collections.swap(path, i, pos);
}
}
}
火柴拼正方形
还记得童话《卖火柴的小女孩》吗？现在，你知道小女孩有多少根火柴，请找出一种能使用所有火柴拼成一个正方形的方法。不能折断火柴，可以把火柴连接起来，并且每根火柴都要用到。
输入为小女孩拥有火柴的数目，每根火柴用其长度表示。输出即为是否能用所有的火柴拼成正方形。
示例 1:
输入: [1,1,2,2,2]
输出: true
解释: 能拼成一个边长为2的正方形，每边两根火柴。
求解：
1）相当于把所有的物体（火柴）往4个容量一样（正方形边长）的容器里放，最后所有的物体都放入容器中，且每个容器刚好满，则成功；
2）对于每个物体往哪个容器里放，依次遍历即可；如果可以放入该容器，并且可以导致最后的成功，则返回true；否则，放入下一个容器中。
3）如果火柴全部放完，此时如果四个容器大小一致，那么则成功；其实只要全部火柴放置完，根据前面的条件，此时四个容器大小必然一致；
4）先对火柴排序，从大数开始放，可以减少回溯的次数；类似于装箱问题的贪婪解法，先放置大体积的物品容易成功。
算法复杂度为。
public static boolean makesquare(int[] nums){
int sum = 0;
for(int num : nums){
sum += num;
}
if(sum % 4 != 0){
return false;
}
int edgeLen = sum / 4;
if(edgeLen <= 0){
return false;
}
// 排序后从大数开始装桶, 会减少回溯次数; 类似装箱问题中, 先装体积大的物品
Arrays.sort(nums);
int[] buckets = new int[4];
return dfs(nums.length-1, nums, edgeLen, buckets);
}
public static boolean dfs(int ind, int[] nums, int len, int[] buckets){
if(ind < 0){
// return true; // 也正确
return buckets[0] == len && buckets[1] == len && buckets[2] == len && buckets[3] == len;
}
for(int i = 0; i<4; i++){
if(buckets[i] + nums[ind] > len){
continue;
}
buckets[i] += nums[ind];
if(dfs(ind-1, nums, len, buckets)){
return true;
}
buckets[i] -= nums[ind];
}
return false;
}
单词拆分
给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
说明：
拆分时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。
示例 1：
输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。
示例 2：
输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
注意你可以重复使用字典中的单词。
示例 3：
输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false
记忆化回溯（记录子问题的解，避免重复计算）
我们可以使用记忆化的方法，其中一个 memo数组会被用来保存子问题的结果。每当访问到已经访问过的后缀串，直接用 memo数组中的值返回而不需要继续调用函数。
通过记忆化，许多冗余的子问题可以极大被优化，回溯树得到了剪枝，因此极大减小了时间复杂度。
时间复杂度；空间复杂度
public static boolean wordBreak(String s, List<String> wordDict) {
Boolean[] results = new Boolean[s.length()];
return dfs(s, wordDict, 0, results);
}
public static boolean dfs(String s, List<String> wordDict, int start, Boolean[] result){
if(start == s.length()){
return true;
}
if(result[start] != null){
return result[start];
}
for(int end = start + 1; end <= s.length(); end++){
if(wordDict.contains(s.substring(start, end)) && dfs(s, wordDict, end, result)){
result[start] = true; // 记录答案, 以免重复计算子问题
return true;
}
}
result[start] = false;// 记录答案, 以免重复计算子问题
return false;
}
组合总和
回溯（剪枝）
1）避免重复，需要设置一个起始下标start；
2）path全局只有一个引用，所以加入ans时需要new新对象。
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> ans = new ArrayList<>();
Arrays.sort(candidates);
backtrace(ans, new ArrayList<>(), candidates, 0, target, 0);
return ans;
}
public void backtrace(List<List<Integer>> ans, List<Integer> path, int[] candidates, int sum, int target, int start) {
if (sum == target) {
ans.add(new ArrayList<>(path));
}
// 剪枝
if (sum > target) {
return;
}
for (int i = start; i < candidates.length; i++) {
// 剪枝
if (sum + candidates[i] > target) {
break;
}
// 选择
sum += candidates[i];
path.add(candidates[i]);
// 回溯
backtrace(ans, path, candidates, sum, target, i);
sum -= candidates[i];
// 撤销选择
path.remove(path.size() - 1);
}
return;
}
组合总和 II
回溯解法
1）先不考虑任何剪枝的代码，按照回溯框架写出回溯代码；
2）利用提前排序，进行各种剪枝；
private int[] candidates;
private List<List<Integer>> ans;
private int target;
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
this.ans = new ArrayList<>();
this.target = target;
this.candidates = candidates;
if(candidates.length == 0){
return ans;
}
Arrays.sort(candidates);
backtrace(new ArrayList<>(), 0, 0);
return ans;
}
public void backtrace(List<Integer> integers, int sum, int k) {
if (sum == target) {
List<Integer> list = new ArrayList<>(integers);
ans.add(list);
return;
}
// 剪枝
if(sum > target){
return;
}
for (int i = k; i < candidates.length; i++) {
// 剪枝
if(sum + candidates[i] > target){
break;
}
// 剪枝
if(i > k && candidates[i] == candidates[i-1]){
continue;
}
integers.add(candidates[i]);
backtrace(integers, sum + candidates[i], i + 1);
integers.remove(integers.size() - 1);
}
}
}
电话号码的字母组合
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例:
输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
说明:
尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。
回溯
private static String[] cc = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
public static List<String> letterCombinations(String digits) {
if(digits.length() == 0){
return new ArrayList<>();
}
List<String> ret = new ArrayList<>();
List<String> words = new ArrayList<>();
for(int i=0; i<digits.length(); i++){
int index = digits.charAt(i) - '0';
words.add(cc[index]);
}
backtrace(ret, new ArrayList<>(), words, 0);
return ret;
}
public static void backtrace(List<String> ret, List<Character> comb, List<String> words, int wordInd){
if(wordInd > words.size()-1){
ret.add(listToString(comb));
return;
}
String word = words.get(wordInd);
for(int i=0; i<word.length(); i++){
comb.add(word.charAt(i));
backtrace(ret, comb, words, wordInd+1);
comb.remove(comb.size()-1);
}
}
public static String listToString(List<Character> comb){
StringBuilder sb = new StringBuilder();
for(int i=0; i<comb.size(); i++){
sb.append(comb.get(i));
}
return sb.toString();
}
复原IP地址
回溯算法
1）路径：即构成IP的4个数字的集合：segs，由分割点落下的位置决定；
2）选择列表：即分割点落下的位置，或者每个seg结束的位置。所以需要保留每个分割点开始的位置索引：sInd，每次的seg结束位置选择都有三个：sInd+1,sInd+2,sInd+3；
3）返回条件：集齐构成IP的4个数字，且s被遍历完；
同时注意剪枝：
1）如果发现选择完一个数字后，后面的数字位数明显不可能满足IP的条件，直接break；
2）三位数不能超过255；两位数或者三位数不能以'0'开头；
public static List<String> restoreIpAddresses(String s) {
List<String> ips = new ArrayList<>();
backtrace(ips, s, new ArrayList<>(), 0);
return ips;
}
public static void backtrace(List<String> ips, String s, List<String> segs, int sInd){
if(segs.size() == 4){
if(sInd == s.length()){
ips.add(String.join(".", segs));
}
return;
}
for(int end = sInd + 1; end <= sInd + 3 && end <= s.length(); end++){
String ipSeg = s.substring(sInd, end);
// 剪枝
int leftLength = s.length() - end;
int leftCount = 4 - segs.size() - 1;
if(leftLength < leftCount || leftLength > leftCount * 3){
continue;
}
// 三位数不能超过255
if(end == sInd + 3 && ipSeg.compareTo("255") > 0){
break;
}
// 二位数/三位数不能以0开头
if(end > sInd + 1 && ipSeg.startsWith("0")){
break;
}
segs.add(ipSeg);
backtrace(ips, s, segs, end);
segs.remove(segs.size()-1);
}
}
括号生成
回溯算法
剪枝：
1）左括号可选条件：只要左括号还有剩余，就可以选择；
2）有括号可选条件：目前已经选择的左括号的数量大于右括号的数量，所以需要两个变量分别保存已经选择的左括号的数量和右括号的数量。
class Solution {
public List<String> generateParenthesis(int n) {
List<String> ans = new ArrayList();
backtrack(ans, new StringBuilder(), 0, 0, n);
return ans;
}
public void backtrack(List<String> ans, StringBuilder cur, int open, int close, int max){
if (cur.length() == max * 2) {
ans.add(cur.toString());
return;
}
if (open < max) {
cur.append('(');
backtrack(ans, cur, open+1, close, max);
cur.deleteCharAt(cur.length() - 1);
}
if (close < open) {
cur.append(')');
backtrack(ans, cur, open, close+1, max);
cur.deleteCharAt(cur.length() - 1);
}
}
}
路径总和 II
public static List<List<Integer>> pathSum(TreeNode root, int sum) {
List<List<Integer>> paths = new ArrayList<>();
if(root == null){
return paths;
}
List<Integer> path = new ArrayList<>();
path.add(root.val);
dfs(paths, path, sum, root.val, root);
return paths;
}
public static void dfs(List<List<Integer>> paths, List<Integer> path, int target, int sum, TreeNode root){
if(sum == target && root.left == null && root.right == null){
paths.add(new ArrayList<>(path));
return;
}
if(root.left != null){
sum += root.left.val;
path.add(root.left.val);
dfs(paths, path, target, sum, root.left);
sum -= root.left.val;
path.remove(path.size()-1);
}
if(root.right != null){
sum += root.right.val;
path.add(root.right.val);
dfs(paths, path, target, sum, root.right);
sum -= root.right.val;
path.remove(path.size()-1);
}
}
路径总和 III
回溯算法
- 前缀和：题中所求部分路径之和 = 全部路径之和 - 前缀路径之和；即 target = pathSum - prefixSum；所以遍历到当前节点时，只需判断截止到当前节点的pathSum ?= target + prefixSum。考虑到前缀和可能有相同值，所以需要记录数量。
- 回溯：回到当前层时，需要恢复前缀和Map。
private int count;
public int pathSum(TreeNode root, int sum) {
if(root == null){
return 0;
}
count = 0;
Map<Integer, Integer> prefixSumCount = new HashMap<>();
prefixSumCount.put(0, 1);
backtrace(root, prefixSumCount, 0, sum);
return count;
}
public void backtrace(TreeNode node, Map<Integer, Integer> prefixSumCount, int pathSum, int target){
if(node == null){
return;
}
pathSum += node.val;
count += prefixSumCount.getOrDefault(pathSum - target, 0);
prefixSumCount.put(pathSum, prefixSumCount.getOrDefault(pathSum, 0) + 1);
backtrace(node.left, prefixSumCount, pathSum, target);
backtrace(node.right, prefixSumCount, pathSum, target);
prefixSumCount.put(pathSum, prefixSumCount.get(pathSum) - 1);
}
组合
回溯
public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> ans = new ArrayList<>();
backtrace(ans, new ArrayList<>(), n, 0, k);
return ans;
}
public void backtrace(List<List<Integer>> ans, List<Integer> path, int n, int num, int k){
if(path.size() == k){
ans.add(new ArrayList<>(path));
return;
}
// 剪枝:当后面所有的数的个数都加入path，仍然小于k个，可以返回
if(k - path.size() > n - num){
return;
}
for(int i = num + 1; i <= n; i ++){
path.add(i);
backtrace(ans, path, n, i, k);
path.remove(path.size()-1);
}
}
安卓系统手势解锁
回溯
1）列举出下一步棋可能的方向：总共8组，16个方向；容易漏掉馬字格的8个方向。
2）每个方向上，判断下一步落脚点是否已经被访问，如果已经访问过，那么在这个方向上继续一步，直至在这个方向上找到一个未访问的落脚点。如果找到，那么可以作为下一步的位置；如果超出范围仍未找到，那么这个方向无效。（实际上每个方向上最多连续走两步）
3）技巧：涉及走棋的题目，往往涉及到数字和方格中位置的转换技巧，通过除法取余和取整可以分别得到行号和列号。
由数字得到位置: num => [(num-1)/3][(num-1)%3]
由位置得到数字: [i][j] => i * 3 + j + 1;
4）利用对称进行优化，本题从1开始的手势总数和从3,7,9开始是一样的；从2开始的手势总数和从4,6,8开始是一样的；剩下最后一种从5开始的。
public class Solution {
private int total;
// 16 个方向
public static int[][] directions = {
{0, 1}, {0, -1},
{1, 0}, {-1, 0},
{1, 1}, {-1, -1},
{-1, 1}, {1, -1},
{1, 2}, {-1, -2},
{2, 1}, {-2, -1},
{-1, 2}, {2, -1},
{1, -2}, {-2, 1}};
public int numberOfPatterns(int m, int n) {
int ans = 0;
ans += getNumberOfPatterns(1, m, n) * 4; // 1,3,7,9
ans += getNumberOfPatterns(2, m, n) * 4; // 2,4,6,8
ans += getNumberOfPatterns(5, m, n); // 5
return ans;
}
public int getNumberOfPatterns(int start, int m, int n){
total = 0;
boolean[] visit = new boolean[10];
visit[start] = true;
backtrace(1, start, visit, m, n);
return total;
}
public void backtrace(int currentCount, int currentNum, boolean[] visit, int m, int n) {
if (currentCount >= m && currentCount <= n) {
total++;
}
if (currentCount >= n) {
return;
}
int currentRow = (currentNum - 1) / 3;
int currentCol = (currentNum - 1) % 3;
for (int[] direction : directions) {
int nextRow;
int nextCol;
int tempRow = currentRow;
int tempCol = currentCol;
// 确定这个方向上是否有满足条件的下一个落脚点
boolean hasNextPos = true;
while (true){
nextRow = tempRow + direction[0];
nextCol = tempCol + direction[1];
if(nextRow >= 0 && nextRow <= 2 && nextCol >= 0 && nextCol <= 2){
int nextNum = nextRow * 3 + nextCol + 1;
if(!visit[nextNum]){
break;
}
tempRow = nextRow;
tempCol = nextCol;
}else {
hasNextPos = false;
break;
}
}
// 回溯迭代
if(hasNextPos){
int nextNum = nextRow * 3 + nextCol + 1;
visit[nextNum] = true;
currentCount++;
backtrace(currentCount, nextNum, visit, m, n);
currentCount--;
visit[nextNum] = false;
}
}
}
二叉树中和为某一值的路径
回溯
- 正向思维，记录当前路径的和；注意作为参数的变量，在回溯调用之前和之后必须保持一致，所以在添加path到ans的时候，将当前节点的值加入的是刚new出来的rightAns中，而不是先加入path，再付给rightAns。
public List<List<Integer>> pathSum(TreeNode root, int sum) {
List<List<Integer>> ans = new ArrayList<>();
if(root == null){
return ans;
}
dfs(ans, new ArrayList<>(), root, 0, sum);
return ans;
}
public void dfs(List<List<Integer>> ans, List<Integer> path, TreeNode current, int pathSum, int sum){
if(pathSum + current.val == sum && current.left == null && current.right == null){
List<Integer> rightAns = new ArrayList<>(path);
rightAns.add(current.val);
ans.add(rightAns);
return;
}
if(current.left != null){
path.add(current.val);
dfs(ans, path, current.left, pathSum + current.val, sum);
path.remove(path.size()-1);
}
if(current.right != null){
path.add(current.val);
dfs(ans, path, current.right, pathSum + current.val, sum);
path.remove(path.size()-1);
}
}
- 逆向思维，记录剩下的路径值。
public void dfs(List<List<Integer>> ans, List<Integer> path, TreeNode current, int diff){
if(current == null){
return;
}
path.add(current.val);
diff -= current.val;
if(diff == 0 && current.left == null && current.right == null){
ans.add(new ArrayList<>(path));
}
dfs(ans, path, current.left, diff);
dfs(ans, path, current.right, diff);
path.remove(path.size()-1);
}
可能的二分法
深度优先
这里是纯深度优先算法，没有任何回溯，也不需要回溯；
- dislikes关系可以用邻接矩阵表示；
- 数字分组的过程可以映射成给数字染色的过程，相邻节点（数字）之间必须异色；
- 可以从1到N，逐一进行深度优先染色，dfs函数表示：给某个数字染成某种颜色，是否能够成功；如果从1到N都染色成功，则返回true；否则，返回false；
- dfs函数在给某个数字染色的时候，需要将邻居染成异色；如果染色之前发现自己已经是异色了，则矛盾，返回false；如果发现自己已经是同色了，则已经完成了染色，返回true；
- 技巧：可以使用数字1和-1表示异色，0表示未染色，这样可以使用一个数组保存所有节点染色情况。
public boolean possibleBipartition(int N, int[][] dislikes) {
List<Integer>[] table = new ArrayList[N + 1];
for (int i = 1; i <= N; i++) {
table[i] = new ArrayList<>();
}
for (int i = 0; i < dislikes.length; i++) {
int[] dis = dislikes[i];
int num0 = dis[0];
int num1 = dis[1];
table[num0].add(num1);
table[num1].add(num0);
}
int[] colored = new int[N+1]; // 0未染色, 1和-1代表相反的两种颜色
for(int number = 1; number <= N; number ++){
if(colored[number] != 0){ // 已经染过色, 下一个
continue;
}
// 对number进行深度优先染色: 注意既然前面所有的节点的深度优先染色都没有使number着色,
// 说明这个number与所有number都不是邻居关系(即dislike关系)，所以这里随便染成1或者-1都是正确的
if(!dfs(number, 1, colored, table)){
return false;
}
}
return true;
}
// 深度优先染色: color为-1/+1
public boolean dfs(int number, int color, int[] colored, List<Integer>[] table) {
if(colored[number] == -color){
return false;
}
if(colored[number] == color){
return true;
}
colored[number] = color; // 染色
for(int neighbor : table[number]){
if(!dfs(neighbor, -color, colored, table)){
return false;
}
}
return true;
}
子集 II
- 同层去重
i > index && nums[i] == nums[i-1]
- 剪枝
- 按子集个数遍历回溯函数
public List<List<Integer>> subsetsWithDup(int[] nums) {
List<List<Integer>> ans = new ArrayList<>();
Arrays.sort(nums);
for(int count = 0; count <= nums.length; count++){
backtrace(ans, new ArrayList<>(), count, nums, 0);
}
return ans;
}
public void backtrace(List<List<Integer>> ans, List<Integer> sub, int count, int[] nums, int index){
if(sub.size() == count){
ans.add(new ArrayList<>(sub));
return;
}
// 剪枝
if(sub.size() + nums.length - index < count){
return;
}
for(int i=index; i<nums.length; i++){
// 同层去重
if(i > index && nums[i] == nums[i-1]){
continue;
}
sub.add(nums[i]);
backtrace(ans, sub, count, nums, i+1);
sub.remove(sub.size()-1);
}
}
字符串的排列
回溯算法
- 关键是如何通过剪枝去重：排序后去重：前后相邻的元素如果相同，那么这些相同的连续元素中，只需要固定一次；一般选择固定第一个元素，后面相同的元素不再固定。程序中判断是否是第一个固定的元素，通过判断前一个元素是否访问过决定：如果前一个相同的元素已经访问过，说明是这些相同的元素都是第一次固定，否则就是第二次固定；
if (i > 0 && chars[i] == chars[i - 1] && !visit[i - 1]) {
continue;
}
public String[] permutation(String s) {
char[] chars = s.toCharArray();
Arrays.sort(chars);
List<String> ans = new ArrayList<>();
backtrace(ans, new StringBuilder(), chars, new boolean[s.length()]);
String[] ret = new String[ans.size()];
for (int i = 0; i < ans.size(); i++) {
ret[i] = ans.get(i);
}
return ret;
}
public void backtrace(List<String> ans, StringBuilder sb, char[] chars, boolean[] visit) {
if (sb.length() == chars.length) {
String s = new StringBuilder(sb).toString();
ans.add(s);
return;
}
for (int i = 0; i < chars.length; i++) {
if (visit[i]) {
continue;
}
// 去重(剪枝)
if (i > 0 && chars[i] == chars[i - 1] && !visit[i - 1]) {
continue;
}
sb.append(chars[i]);
visit[i] = true;
backtrace(ans, sb, chars, visit);
visit[i] = false;
sb.deleteCharAt(sb.length() - 1);
}
}
- 另一种更加高效的写法（算法的时间复杂度一样），即另一种实现操作：是利用交换元素的操作，代替上面sb.append的操作。这种swap的操作在很多算法或技巧的实现中都用到了，所以建议必须掌握。
- 原理：想要得到某数组的一个全排列，一种做法是新建一个数组，然后从原数组中依次取元素到新数组空间中，待原数组的元素都取光了，新数组就是原数组的一个全排列，可以用visit数组记录原数组哪些元素被取过，哪些元素没有被取过。另一种做法是，不用新建一个数组，在原数组进行操作：依次固定第i个元素，固定的方法是从（i~length-1）元素中任取一个位置x上的元素放到第i个元素的位置上（即swap(i, x)），当固定到最后一个元素时，就得到原数组的一个全排列。
- 具体的过程为
1）固定第0个元素，从(0~length-1)中选取位置x，然后交换元素swap(0, x)，即将位置x上的元素放置到位置0处；
2）然后固定第1个元素，因为第0个元素已经被固定了，所以第1个元素的候选者只能从(1~length-1)中选取位置x，然后交换元素swap(1, x)，即将位置x上的元素放置到1处；
3）依次类推，当固定到第length-1个元素时，候选者只剩第length-1位置上的元素了，此刻得到原数组的全排列。 - 代码如下，几点说明
1）backtrace方法的参数为pos，作用即为固定pos位置的数；
2）这里去重的方法就比较容易理解多了：pos位置的数如果选取到了重复的数，则过滤；而且不再需要将原数组进行排序。
public class Solution {
List<String> res = new LinkedList<>();
char[] c;
public String[] permutation(String s) {
c = s.toCharArray();
backtrace(0);
return res.toArray(new String[res.size()]);
}
void backtrace(int pos) {
if (pos == c.length - 1) {
res.add(String.valueOf(c));
return;
}
HashSet<Character> set = new HashSet<>();
for (int i = pos; i < c.length; i++) {
if (set.contains(c[i])) {
continue; // 重复，因此剪枝
}
set.add(c[i]);
swap(i, pos); // 交换，将 c[i] 固定在第 pos 位
backtrace(pos + 1); // 开启固定第 pos + 1 位字符
swap(i, pos); // 恢复交换
}
}
void swap(int a, int b) {
char tmp = c[a];
c[a] = c[b];
c[b] = tmp;
}
}
