代码随想录算法训练营第二十二天

LeetCode.77 组合

题目链接 组合

题解

class Solution {
    List<List<Integer>> result= new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> combine(int n, int k) {
        dfs(n,k,1);
        return result;
    }
    public void dfs(int n,int k,int count){
        if(path.size() == k) {
            result.add(new ArrayList<>(path));
            return ;
        }
        for(int i = count;i<=n;i++){
            path.add(i);
            dfs(n,k,i+1);
            path.removeLast();
        }
    }
}

解题思路

这段代码实现了组合问题的求解，即从 1 到 n 中选取 k 个数字的所有可能组合，使用了深度优先搜索（DFS）和回溯算法的思想。

代码的主要逻辑如下：

1. 定义了两个成员变量：

   • result：用于存储所有符合条件的组合
   • path：用于递归过程中临时间结果，存储当前正在构建的组合

2. combine方法是入口函数：

   • 接收两个参数 n（范围上限）和 k（选取的数字个数）
   • 调用 dfs 方法开始深度优先搜索
   • 返回最终的结果集

3. dfs方法是核心递归函数：

   • 参数 count 表示当前开始考虑的数字（用于避免重复组合）
   • 递归终止条件：当 path 的大小等于 k 时，说明找到了一个有效组合，将其加入 result
   • 循环从 count 到 n，尝试将每个数字加入当前组合：
     • 将数字 i 加入 path
     • 递归调用 dfs，注意下一次搜索从 i+1 开始（保证组合的有序性，避免重复）
     • 回溯：移除 path 中最后加入的数字，尝试其他可能性

这个算法的时间复杂度是 O (C (n,k)×k)，其中 C (n,k) 是组合数，空间复杂度是 O (k)（递归栈深度和 path 的大小）。

LeetCode.216 组合总和III

题目链接 组合总和III

题解

class Solution {
    List<List<Integer>> resList = new ArrayList<List<Integer>>();
    List<Integer> res = new ArrayList<>();
    public List<List<Integer>> combinationSum3(int k, int n) {
        if(n < k * (k + 1) /2) return resList;
        if(n > 45) return resList;
        dfs(k,n,0,1);
        return resList;
    }
    public void dfs(int k,int n,int sum,int index){
        if(sum > n) return ;
        if(res.size() == k){
            if(sum == n)  resList.add(new ArrayList<>(res));
            return;
        }
        for(int i = index;i<=9;i++){
            res.add(i);
            sum += i;
            dfs(k,n,sum,i+1);
            sum-=i;
            res.remove(res.size()-1);
        }
    }
}

解题思路

这段代码实现了 "组合总和 III" 的问题求解，即从 1 到 9 中选取 k 个不重复的数字，使得它们的和等于 n，找出所有可能的组合。

代码的主要逻辑如下：

1. 定义了两个成员变量：

   • resList：用于存储所有符合条件的组合
   • res：用于递归过程中存储当前正在构建的组合

2. combinationSum3方法是入口函数：

   • 首先进行了两个边界条件判断：
     • 如果 n 小于 1 到 k 的最小和（k*(k+1)/2），直接返回空结果
     • 如果 n 大于 9 个数的最大和（45），直接返回空结果
   • 调用 dfs 方法开始深度优先搜索
   • 返回最终的结果集

3. dfs方法是核心递归函数：

   • 参数说明：
     • k：需要选取的数字个数
     • n：目标和
     • sum：当前组合的数字和
     • index：当前开始考虑的数字（避免重复组合）
   • 剪枝操作：如果当前和已经大于 n，直接返回
   • 递归终止条件：当 res 的大小等于 k 时，检查和是否等于 n，如果是则加入结果集
   • 循环从 index 到 9，尝试将每个数字加入当前组合：
     • 将数字 i 加入 res
     • 将 i 累加到 sum 中
     • 递归调用 dfs，下一次搜索从 i+1 开始（保证数字不重复）
     • 回溯：从 sum 中减去 i，从 res 中移除最后加入的数字，尝试其他可能性

这个算法通过回溯法高效地搜索所有可能的组合，并通过剪枝操作减少不必要的计算，提高了效率。

LeetCode.17 电话号码的字母组合

题目链接 电话号码的字母组合

题解

import java.util.ArrayList;
import java.util.List;

class Solution {
    // 数字到字母的映射表，索引对应数字
    private static final String[] LETTER_MAP = {
        "",     // 0
        "",     // 1
        "abc",  // 2
        "def",  // 3
        "ghi",  // 4
        "jkl",  // 5
        "mno",  // 6
        "pqrs", // 7
        "tuv",  // 8
        "wxyz"  // 9
    };
    
    List<String> resList = new ArrayList<>();
    StringBuilder sb = new StringBuilder();
    
    public List<String> letterCombinations(String digits) {
        if (digits == null || digits.length() == 0) {
            return resList;
        }
        dfs(digits, 0);
        return resList;
    }
    
    public void dfs(String digits, int index) {
        // 递归终止条件：已处理完所有数字
        if (index == digits.length()) {
            resList.add(sb.toString());
            return;
        }
        
        // 获取当前数字对应的字母
        char digit = digits.charAt(index);
        // 检查是否是有效的数字字符
        if (digit < '0' || digit > '9') {
            return;
        }
        String letters = LETTER_MAP[digit - '0'];
        
        // 遍历所有可能的字母
        for (int i = 0; i < letters.length(); i++) {
            sb.append(letters.charAt(i));
            dfs(digits, index + 1);
            // 回溯：删除最后一个字符
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}

解题思路

这段代码实现了电话号码的字母组合问题，即根据输入的数字字符串，返回所有可能的字母组合。这是一个经典的回溯算法应用场景。

代码的主要逻辑如下：

1. 首先定义了一个静态数组LETTER_MAP，存储了数字 0-9 对应的字母，其中：

   • 0 和 1 没有对应的字母（空字符串）
   • 2 对应 "abc"，3 对应 "def"，以此类推
   • 7 对应 "pqrs"，9 对应 "wxyz"（这两个数字对应 4 个字母）

2. 定义了两个成员变量：

   • resList：用于存储所有可能的字母组合结果
   • sb：StringBuilder对象，用于在递归过程中构建当前的字母组合

3. letterCombinations方法是入口函数：

   • 首先处理边界情况，如果输入为空或长度为 0，直接返回空列表
   • 调用dfs方法开始深度优先搜索
   • 返回最终的结果集

4. dfs方法是核心递归函数：

   • 参数index表示当前正在处理的数字在输入字符串中的位置
   • 递归终止条件：当index等于输入字符串长度时，说明已处理完所有数字，将当前构建的组合加入结果集
   • 获取当前数字对应的字母字符串
   • 遍历该字符串中的每个字母：
     • 将字母添加到StringBuilder中
     • 递归处理下一个数字（index + 1）
     • 回溯：删除StringBuilder中最后添加的字母，尝试其他可能性

这个算法通过回溯法穷举了所有可能的字母组合，时间复杂度是 O (3^m * 4^n)，其中 m 是对应 3 个字母的数字个数，n 是对应 4 个字母的数字个数（7 和 9）。