经典算法之回溯算法

文章目录

一、问题描述

二、解题思路与代码

三、回溯算法模板总结

---

活动地址：21天学习挑战赛

一、问题描述

你有一套活字字模tiles，其中每个字模上都刻有一个字母tiles[i]。返回你可以印出的

非空字母序列的数目。 （ 注意：本题中，每个活字字模只能使用一次）

输入：“AAB”

输出：8

解释：所有可能的序列为：“A”,“B”,“AA”，“AB”，“BA”，“AAB”，“ABA”，“BAA”

输入：“AAABBC”

输出：188

1.   1 < = t i l e s . l e n g t h < = 7
2. t i l e s 由大写英文字母组成

---

 

二、解题思路与代码

本题实际上是求输入的字符可以组成多少种不同的组合

 

 以上图为例来讲解一下本题的解题思路：

if (i - 1 >= 0 && chars[i] == chars[i - 1] && !used[i - 1])
    continue;

解题代码（附测试类）：

package TwentyOne_Challenge;
import java.util.Arrays;
public class DayTen {
    public static void main(String[] args) {
        String tiles="AAB";
        System.out.println("AAB模板可以印出的非空字母序列的数目为："+TilesSonNumber(tiles));
        System.out.println("AAABBC模板可以印出的非空字母序列的数目为："+TilesSonNumber("AAABBC"));
        System.out.println("ABCDEF模板可以印出的非空字母序列的数目为："+TilesSonNumber("ABCDEF"));
    }
      private static int TilesSonNumber(String tiles) {
         char[] chars = tiles.toCharArray();
         //先排序，目的是让相同的字符挨着，在下面计算的时候好过滤掉重复的
         Arrays.sort(chars);
         int[] res = new int[1];
         backtrack(res, chars, new boolean[tiles.length()], tiles.length(), 0);
         return res[0];
         }
 
      private static void backtrack(int[] res, char[] chars, boolean[] used, int length, int index) {
         //如果没有可以选择的就返回
         if (index == length)
             return;
         //注意，这里的i每次都是从0开始的，不是从index开始
         for (int i = 0; i < length; i++) {
         //一个字符只能选择一次，如果当前字符已经选择了，就不能再选了。
         if (used[i])
             continue;
         //过滤掉重复的结果
         if (i - 1 >= 0 && chars[i] == chars[i - 1] && !used[i - 1])
             continue;
         //选择当前字符，并把它标记为已选择
         used[i] = true;
         res[0]++;//选择一个字符，就多了一种结果
         //下一分支继续递归
         backtrack(res, chars, used, length, index + 1);
         //使用完之后再把它给复原。
         used[i] = false;
         }
     }
}

 

---

 

三、回溯算法模板总结

private void backtrack("原始参数") {
  //终止条件(递归必须要有终止条件)
  if ("终止条件") {
  //一些逻辑操作（可有可无，视情况而定）
  return;
  }
 
  for (int i = "for循环开始的参数"; i < "for循环结束的参数"; i++) {
  //一些逻辑操作（可有可无，视情况而定）
 
 //做出选择
 
 //递归
 backtrack("新的参数");
 //一些逻辑操作（可有可无，视情况而定）
 
 //撤销选择
 }
}

回溯算法，通俗地解释就是不断的尝试，如果不成功，再继续回到上一步继续尝试直至成功，

它的原理就是一个不断尝试的过程，这很励志。