• LeetCode刷题笔记之回溯算法（一）

    一、回溯算法的基础知识

    1. 回溯算法本质上是一种穷举算法，回溯算法一定伴随着递归，回溯算法就是遍历树枝。
    2. 站在回溯树的一个节点上，你只需要思考 3 个问题：
      • 路径：也就是已经做出的选择；
      • 选择列表：也就是你当前可以做的选择；
      • 结束条件：也就是到达决策树底层，无法再做选择的条件。
    3. 回溯算法的模板：
    List result = new ArrayList();
public void backtrack(路径, 选择列表){
    if(满足结束条件){
		result.add(路径);
        return;
	}
    
    for(选择 : 选择列表){ //层序遍历
        做选择;
        backtrack(路径, 选择列表); //递归遍历
        撤销选择;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    1. 需要使用回溯算法解决的问题：
      • 组合问题：N个数里面按一定规则找出k个数的集合；
      • 切割问题：一个字符串按一定规则有几种切割方式；
      • 子集问题：一个N个数的集合里有多少符合条件的子集；
      • 排列问题：N个数按一定规则全排列，有几种排列方式；
      • 棋盘问题：N皇后，解数独等等

    二、组合问题

    组合是无序的，即{1，2}与{2，1}是同一个组合。

    1. 77【组合】

    • 题目： 给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。你可以按任何顺序返回答案。
    • 代码：
    class Solution {
    public List<Integer> path = new LinkedList<>();
    public List<List<Integer>> ansList = new LinkedList<>();
    public List<List<Integer>> combine(int n, int k) {
        //首先确定回溯法构造的树的根下面第一层是n个节点，即for循环的判别条件是<=n
        //终止条件是每条路径包含k个元素
        //需要进行剪枝，当剩余元素无法满足path.size()==k，是推出循环
        backtrack(n,k,1);
        return ansList;
    }
    public void backtrack(int n, int k, int index){
        if(path.size() == k){
            ansList.add(new ArrayList<>(path));//不能直接将path加入anList，因为path是引用类型
            return;
        }
        for (int i = index; i <= n-(k-path.size())+1; i++) {
            path.add(i);
            backtrack(n,k,i+1);
            path.removeLast();
        }
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22

    2. 216【组合总和III】

    • 题目： 找出所有相加之和为 n 的 k 个数的组合，且满足下列条件。返回所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。
      • 只使用数字1到9；
      • 每个数字 最多使用一次。
    • 代码：
    class Solution {
    public List<Integer> path = new LinkedList<>();
    public List<List<Integer>> ansList = new ArrayList<>();

    public List<List<Integer>> combinationSum3(int k, int n) {
        //终止条件是path中包含k个数
        //构造的树的根下面的第一层包含[1,9]
        backtrack(k,n,1);
        return ansList;
    }
    public void backtrack(int k,int n,int index){
        if(path.size()==k){
            int sums = 0;
            for (int i = 0; i < k; i++) {
                sums += path.get(i);
            }
            if(sums == n){
                ansList.add(new ArrayList<>(path));
            }
            return;
        }

        for (int i = index; i <= 9-(k-path.size())+1 ; i++) {
            path.add(i);
            backtrack(k,n,i+1);
            path.removeLast();
        }
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29

    3. 17【电话号码的字母组合】

    • 题目： 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按任意顺序返回。给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
    • 代码：
    class Solution {
    public List<String> ansList = new ArrayList<>();
    public StringBuilder path = new StringBuilder();
    HashMap<Character,String> map = new HashMap<>();
    public List<String> letterCombinations(String digits) {
        //首先使用map存储每个数字对应的字符串
        //这里的循环需要进行次数为每个输入数字所表示的字符串的长度
        //递归次数为输入数字字符串的长度
        if(digits.length() == 0) return new ArrayList<>();
        map.put('2',"abc");
        map.put('3',"def");
        map.put('4',"ghi");
        map.put('5',"jkl");
        map.put('6',"mno");
        map.put('7',"pqrs");
        map.put('8',"tuv");
        map.put('9',"wxyz");
        backtrack(digits,digits.length(),0);
        return ansList;
    }
    public void backtrack(String digits,int len,int index){
        //终止条件是path里有len个字符
        if(path.length() == len){
            ansList.add(path.toString());
            return;
        }
        String s = map.get(digits.charAt(index));
        for (int i = 0; i < s.length(); i++) {
            path.append(s.charAt(i));
            backtrack(digits,len,index+1);
            path.deleteCharAt(path.length()-1);
        }
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34

    4. 39【组合总和】

    • 题目： 给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
      candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
      对于给定的输入，保证和为 target 的不同组合数少于 150 个。
    • 代码：
    class Solution {
    public List<List<Integer>> ansList = new ArrayList<>();
    public List<Integer> path = new LinkedList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        //本题的特点是不限制元素出现次数，组合的数量
        //因此，终止条件就为sum>=target
        //另外为了提高效率，在循环时进行剪枝，需要对数组进行排序
        Arrays.sort(candidates);
        backtrack(candidates,target,0,0);
        return ansList;
    }
    public void backtrack(int[] candidates, int target, int sum,int index){
        if(sum == target){
            ansList.add(new ArrayList<>(path));
            return;
        }
        for (int i = index; i<candidates.length && sum+candidates[i]<=target; i++) {
            sum += candidates[i];
            path.add(candidates[i]);
            backtrack(candidates,target,sum,i);
            sum -= path.get(path.size()-1);
            path.removeLast();
        }
    }

}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26

    5. 40【组合总和II】

    • 题目： 给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
      candidates 中的每个数字在每个组合中只能使用 一次 。
      注意：解集不能包含重复的组合。
    • 代码：
    class Solution {
    public List<List<Integer>> ansList = new ArrayList<>();
    public List<Integer> path = new LinkedList<>();
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        //本题的与上一题的区别是每个元素只能出现一次
        //因此在排序之后，循环时需要跳过相同的元素
        //并不是所有遇到相同元素的情况就要跳过
        //只有两个节点属于同一递归深度时才跳过
        Arrays.sort(candidates);
        backtrack(candidates,target,0,0);
        return ansList;
    }
    public void backtrack(int[] candidates,int target,int sum,int index){
        if(sum == target){
            ansList.add(new ArrayList<>(path));
            return;
        }
        for(int i=index;i<candidates.length && sum+candidates[i]<=target;i++){
            if(i>index && candidates[i] == candidates[i-1]) continue;
            sum += candidates[i];
            path.add(candidates[i]);
            backtrack(candidates,target,sum,i+1);
            sum -= path.get(path.size()-1);
            path.removeLast();
        }
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27

    三、切割问题

    6. 131【分割回文串】

    • 题目： 给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
      回文串 是正着读和反着读都一样的字符串。
    • 代码：
    class Solution {
    List<List<String>> ansList = new ArrayList<>();
    List<String> path = new LinkedList<>();
    public List<List<String>> partition(String s) {
        //第i层选取从第i个元素为起始点进行分割，
        //因此，需要记录每次进行分割的起始点
        //递归时要将起始点+1
        //每次分割都要判断当前部分是否满足回文串的要求
        //终止条件是起始点到最后一个元素
        backtrack(s,0);
        return ansList;
    }
    public void backtrack(String s,int index){
        if(index >= s.length()){
            ansList.add(new ArrayList<>(path));
            return;
        }
        for(int i=index;i<s.length();i++){
            String subStr = s.substring(index,i+1);
            if(!isPalindrome(subStr)){
                continue;
            }else{
                path.add(subStr);
            }
            backtrack(s,i+1);
            path.removeLast();
        }
    }
    public boolean isPalindrome(String str){
        for (int i = 0, j=str.length()-1; i < j; i++,j--) {
            if(str.charAt(i) != str.charAt(j)){
                return false;
            }
        }
        return true;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37

    7. 93【复原IP地址】

    • 题目： 有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 ‘.’ 分隔。
      例如：“0.1.2.201” 和 “192.168.1.1” 是 有效 IP 地址，但是 “0.011.255.245”、“192.168.1.312” 和 “192.168@1.1” 是 无效 IP 地址。
      给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 ‘.’ 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。
    • 代码：
    class Solution {
    public List<String> ansList = new ArrayList<>();
    public List<String> restoreIpAddresses(String s) {
        //和上一题相似，需要对字符串进行分割
        //终止条件是出现了3个.，即分割3次
        backtrack(s,0,0);
        return ansList;
    }
    public void backtrack(String s, int index, int pointNum){
        if(pointNum == 3){
            if(isValid(s.substring(index))){
                ansList.add(s);
            }
            return;
        }
        for (int i = index; i < s.length(); i++) {
            String str = s.substring(index,i+1);
            if(!isValid(str) || i+1==s.length()){
                break;
            }else{
                str = s.substring(0,i+1)+"."+s.substring(i+1);
                pointNum++;
                backtrack(str,i+2,pointNum);
                pointNum--;
                str = s.substring(0,i+1)+s.substring(i+2);
            }
        }
    }
    public boolean isValid(String subStr){
        if(subStr.length()>3 || subStr==""){
            return false;
        }
        if(subStr.length()>1 && subStr.charAt(0)=='0'){
            return false;
        }
        int i = Integer.parseInt(subStr);
        if(i>255){
            return false;
        }
        return true;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42

    四、子集问题

    8. 78【子集】

    • 题目： 给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。解集不能包含重复的子集。你可以按 任意顺序 返回解集。
    • 代码：
    class Solution {
    public List<List<Integer>> ansList = new ArrayList<>();
    public List<Integer> subSet = new LinkedList<>();
    public List<List<Integer>> subsets(int[] nums) {
        //寻找所有子集，意味着需要记录所有节点的值
        ansList.add(new ArrayList<>(subSet));
        backtrack(nums,0);
        return ansList;
    }
    public void backtrack(int[] nums,int index){
        if(index >= nums.length){
            return;
        }
        for (int i = index; i < nums.length; i++) {
            subSet.add(nums[i]);
            ansList.add(new ArrayList<>(subSet));
            backtrack(nums,i+1);
            subSet.removeLast();
        }
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21

    9. 90【子集II】

    • 题目： 给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
      解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
    • 代码：
    class Solution {
    public List<List<Integer>> ansList = new ArrayList<>();
    public List<Integer> subSet = new LinkedList<>();
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        //本题与上一题的区别是有重复元素
        //因此需要对数组进行排序
        Arrays.sort(nums);
        ansList.add(new ArrayList<>(subSet));
        backtrack(nums,0);
        return ansList;
    }
    public void backtrack(int[] nums,int index){
        if(index == nums.length){
            return;
        }
        for (int i = index; i < nums.length; i++) {
            if(i!=index && nums[i] == nums[i-1]){
                continue;
            }
            subSet.add(nums[i]);
            ansList.add(new ArrayList<>(subSet));
            backtrack(nums,i+1);
            subSet.removeLast();
        }
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26

    10. 491【非递减子序列】

    • 题目： 给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。
      数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。
    • 代码：
    class Solution {
    List<List<Integer>> ansList = new ArrayList<>();
    List<Integer> subSet = new LinkedList<>();
    public List<List<Integer>> findSubsequences(int[] nums) {
        //注意题中要求子序列至少有2个元素
        //数组中有重复元素，所以在同一递归层要判断改元素之前是否使用过
        //可以使用map和数组，因为这里数组的值在[-100,100]
        //所以这里使用数组记录某一递归层是否使用过某一元素
        backtrack(nums,0);
        return ansList;
    }
    public void backtrack(int[] nums, int index){
        if(subSet.size() > 1) {
            ansList.add(new ArrayList<>(subSet));
        }
        int[] used = new int[201];
        for(int i=index;i<nums.length;i++){
            if(used[nums[i]+100] == 1) continue;
            if(!subSet.isEmpty() && subSet.get(subSet.size()-1)>nums[i]){
                continue;
            }
            subSet.add(nums[i]);
            used[nums[i]+100] = 1;
            backtrack(nums,i+1);
            subSet.removeLast();
        }
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
  • 相关阅读:
    Vue3 - $attrs 的几种用法（1个或多个根元素、Options API 和 Composition API）
    JDK安装
    Git撤销已经push到远程分支的commit
    【计算机网络实验/wireshark】tcp建立和释放
    Datakit，真正的统一可观测性 Agent
    Elasticsearch与Kibana安装
    谈谈构建有效数据治理策略的十条建议
    构建AR视频空间大数据平台（物联网及工业互联网、视频、AI场景识别）
    选择器知识点詳解
    各种文件对应的文件类型
  • 原文地址：https://blog.csdn.net/weixin_43790779/article/details/136272389