LeetCode回溯算法

回溯模板

 1 private void backtrack("原始参数") {
 2     //终止条件(递归必须要有终止条件)
 3     if ("终止条件") {
 4         //一些逻辑操作（可有可无，视情况而定）
 5         return;
 6     }
 7 
 8     for (int i = "循环开始的参数"; i < "循环结束的参数"; i++) {
 9         //一些逻辑操作（可有可无，视情况而定）
10 
11         //做出选择
12 
13         //递归
14         backtrack("新的参数");
15         //一些逻辑操作（可有可无，视情况而定）
16 
17         //撤销选择
18     }
19 }

剑指 Offer 38. 字符串的排列 - 力扣（LeetCode）

 1 class Solution {
 2     public String[] permutation(String s) {
 3         Set<String> res = new HashSet<>();
 4         backtrack(s.toCharArray(), "", new boolean[s.length()], res);
 5         return res.toArray(new String[res.size()]);
 6     }
 7 
 8     private void backtrack(char[] chars, String tmp, boolean[] visited, Set<String> res) {
 9         if (tmp.length() == chars.length) {
10             res.add(tmp);
11             return;
12         }
13         for (int i = 0; i < chars.length; i++) {
14             if (visited[i]) {
15                 continue;
16             }
17             visited[i] = true;
18             backtrack(chars, tmp + chars[i], visited, res);
19             visited[i] = false;
20         }
21     }
22 }

46. 全排列 - 力扣（LeetCode）

 1 class Solution {
 2     public List<List<Integer>> permute(int[] nums) {
 3         List<List<Integer>> res = new ArrayList<>();
 4         backtrack(nums, new ArrayList<Integer>(), new boolean[nums.length], res);
 5         return res;
 6     }
 7 
 8     private void backtrack(int[] nums, List<Integer> tmp, boolean[] visited, List<List<Integer>> res) {
 9         if (tmp.size() == nums.length) {
10             res.add(new ArrayList<>(tmp));
11             return;
12         }
13         for (int i = 0; i < nums.length; i++) {
14             if (visited[i]) {
15                 continue;
16             }
17             visited[i] = true;
18             tmp.add(nums[i]);
19             backtrack(nums, tmp, visited, res);
20             visited[i] = false;
21             tmp.remove(tmp.size() - 1);
22         }
23     }
24 }

  93. 复原 IP 地址 - 力扣（LeetCode）

 1 class Solution {
 2     List<String> res = new ArrayList<>();
 3     List<String> path = new ArrayList<>();
 4     public List<String> restoreIpAddresses(String s) {
 5         if(s.length()<4 || s.length()>12){
 6             return res;
 7         }
 8         /* 回溯模板，相比于分割字符串只加入分割线一个参数以外，这里还需要添加额外的层数参数level
 9         因为合法的IP地址只有四段，我们不能无限对其进行分割 */
10         backtrack(s,0,0);
11         return res;
12     }
13 
14     // 判断分割出来的每一段字符串是否是合法的IP地址
15     boolean isValidIp(String s){
16         if(s.charAt(0)=='0' && s.length()>1){
17             return false;
18         }
19         if(s.length()>3){
20             return false;
21         }
22         if(Integer.parseInt(s)>255){
23             return false;
24         }
25         return true;
26     }
27 
28     void backtrack(String s,int splitIndex,int level){
29         // 递归终止条件，分割的四个字符串都是合法的IP地址
30         if(level==4){
31             // 在代码的最后再利用join函数加上“.”,构造IP地址的表示形式
32             res.add(String.join(".",path));
33             return;
34         }
35         for(int i=splitIndex;i<s.length();i++){
36             // 每一次分割之后，对剩余字符长度是否合理进行判断，剪枝操作，优化运行速度
37             if((s.length()-i-1) > 3*(3-level)){
38                 continue;
39             }
40             // 如果分割的字符串不是合理的IP地址，跳过
41             if(! isValidIp(s.substring(splitIndex,i+1))){
42                 continue;
43             }
44             // 把合法的IP地址段加入path存储
45             path.add(s.substring(splitIndex,i+1));
46             // 每次把分割线往后移一位，且段数level+1
47             backtrack(s,i+1,level+1);
48             // 进行回溯操作
49             path.remove(path.size()-1);
50         }
51     }
52 }