代码随想录-Day25

216.组合总和III

找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：

只使用数字1到9
每个数字 最多使用一次
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

示例 1:

输入: k = 3, n = 7
输出: [[1,2,4]]
解释:
1 + 2 + 4 = 7
没有其他符合的组合了。
示例 2:

输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
解释:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
没有其他符合的组合了。

方法一：二进制（子集）枚举

class Solution {
    List<Integer> temp = new ArrayList<Integer>();
    List<List<Integer>> ans = new ArrayList<List<Integer>>();

    public List<List<Integer>> combinationSum3(int k, int n) {
        for (int mask = 0; mask < (1 << 9); ++mask) {
            if (check(mask, k, n)) {
                ans.add(new ArrayList<Integer>(temp));
            }
        }
        return ans;
    }

    public boolean check(int mask, int k, int n) {
        temp.clear();
        for (int i = 0; i < 9; ++i) {
            if (((1 << i) & mask) != 0) {
                temp.add(i + 1);
            }
        }
        if (temp.size() != k) {
            return false;
        }
        int sum = 0;
        for (int num : temp) {
            sum += num;
        }
        return sum == n;
    }
}

这段代码也是定义了一个名为 Solution 的类，但这次是解决一个略有不同的组合问题——找出所有和为 n 且正好由 k 个数字组成的序列，这些数字取自 1 到 9 之间的整数，每个数字最多使用一次。这是一种使用位操作优化的组合求解方法。

成员变量

与之前一样，定义了两个成员变量：

• temp：一个 List，用于临时存储当前组合。
• ans：一个 List>，用于存储所有满足条件的组合。

方法

combinationSum3(int k, int n)

• 功能：主方法，接收目标和 n 和组合长度 k 作为参数，返回所有符合条件的组合。
• 过程：通过遍历从 0 到 (1 << 9)（即 2^9）之间所有可能的掩码值（mask），利用 check 方法验证每个掩码是否代表一个有效的组合。如果是，则将该组合添加到答案列表 ans 中。

check(int mask, int k, int n)

• 功能：辅助方法，检查给定的掩码 mask 是否代表一个有效的组合，即组合中的数字个数是否为 k 且这些数字之和为 n。
• 参数：除了掩码 mask 外，还接收组合长度 k 和目标和 n。
• 过程：
  • 首先清空 temp，然后遍历从 0 到 8（代表数字 1 到 9），如果某位在 mask 中被设置（即该位为 1），则将对应的数字（i + 1）添加到 temp 中。
  • 检查 temp 的大小是否等于 k，如果不等直接返回 false。
  • 计算 temp 中所有数字的和，判断这个和是否等于 n，如果相等返回 true，否则返回 false。

这种方法利用位运算高效地枚举了所有可能的选择情况，相比于之前的递归解法，此方法在某些情况下可以减少递归调用的开销，尤其是在处理较大范围的组合问题时更为高效。

方法二：组合枚举

class Solution {
    List<Integer> temp = new ArrayList<Integer>();
    List<List<Integer>> ans = new ArrayList<List<Integer>>();

    public List<List<Integer>> combinationSum3(int k, int n) {
        dfs(1, 9, k, n);
        return ans;
    }

    public void dfs(int cur, int n, int k, int sum) {
        if (temp.size() + (n - cur + 1) < k || temp.size() > k) {
            return;
        }
        if (temp.size() == k) {
            int tempSum = 0;
            for (int num : temp) {
                tempSum += num;
            }
            if (tempSum == sum) {
                ans.add(new ArrayList<Integer>(temp));
                return;
            }
        }
        temp.add(cur);
        dfs(cur + 1, n, k, sum);
        temp.remove(temp.size() - 1);
        dfs(cur + 1, n, k, sum);
    }
}

这段代码是用Java编写的，它定义了一个名为Solution的类，该类包含方法来找出所有组合之和等于特定目标值n的k个不同正整数的组合，且这些整数都在1到n之间（这里限制为1到9，因为题目隐含了这个范围，如dfs函数的第二个参数所示）。这是一个经典的回溯算法应用实例。

方法说明

• combinationSum3(int k, int n): 这是主要的方法，接收两个整数参数k和n，分别代表需要找到的组合的元素个数以及这些元素的和。它初始化调用深度优先搜索(dfs)方法来寻找所有符合条件的组合，并返回存储这些组合的二维列表ans。

• dfs(int cur, int n, int k, int sum): 这是一个递归辅助函数，用于执行深度优先搜索。

  • cur表示当前考虑加入组合的起始数字（递增的基础）。
  • n是可选数字的最大值，在这个上下文中固定为9。
  • k和sum与主方法接收的参数相同，分别代表需要的组合长度和目标和。

  该函数的工作原理如下：

  • 剪枝：首先判断当前路径是否有可能达到解。如果当前临时组合的长度加上剩余数字的数量小于k，或者已经超过k，直接返回，无需继续搜索。
  • 结束条件：当临时组合的长度等于k时，检查这些数字的和是否等于目标sum。如果是，则将当前组合添加到答案列表中，并返回。
  • 递归搜索：尝试选择当前数字cur，将其加入临时组合temp，然后递归调用dfs函数尝试下一个数字。之后通过temp.remove(temp.size() - 1)撤销选择（回溯），再尝试不包含当前数字的情况。

示例解析

假设调用combinationSum3(3, 7)，该函数将寻找所有和为7且包含3个数字的组合，这些数字来自1到9。可能的结果包括[1, 2, 4]。此过程通过深度优先搜索逐层尝试每一种可能的组合，并通过剪枝策略减少无效的搜索路径，从而高效地找到所有解。

方法三：回溯

// 上面剪枝 i <= 9 - (k - path.size()) + 1; 如果还是不清楚
// 也可以改为 if (path.size() > k) return; 执行效率上是一样的
class Solution {
    LinkedList<Integer> path = new LinkedList<>();
    List<List<Integer>> ans = new ArrayList<>();
    public List<List<Integer>> combinationSum3(int k, int n) {
        build(k, n, 1, 0);
        return ans;
    }

    private void build(int k, int n, int startIndex, int sum) {

        if (sum > n) return;

        if (path.size() > k) return;

        if (sum == n && path.size() == k) {
            ans.add(new ArrayList<>(path));
            return;
        }

        for(int i = startIndex; i <= 9; i++) {
            path.add(i);
            sum += i;
            build(k, n, i + 1, sum);
            sum -= i;
            path.removeLast();
        }
    }
}

这段代码同样定义了一个名为 Solution 的类，用于解决找出所有和为 n 且包含恰好 k 个不同数字的组合的问题，其中数字选择范围限定在 1 到 9 之间。与之前版本相比，这段代码采用了一些小的改动和优化，使用了 LinkedList 作为路径的存储结构，以更直观地展示组合构建过程，并在剪枝策略上做了调整。下面是详细的解析：

类成员变量

• LinkedList path：用于保存当前搜索路径上的数字组合。
• List> ans：用于存储所有满足条件的组合。

主方法 combinationSum3(int k, int n)

• 功能：接收目标和 n 和组合长度 k 作为参数，调用 build 方法生成所有符合条件的组合，最后返回所有组合的列表 ans。

辅助方法 build(int k, int n, int startIndex, int sum)

• 功能：递归构建组合。接收当前需要的组合长度 k、目标和 n、搜索起始数字 startIndex 以及当前路径和 sum 作为参数。
• 剪枝条件：
  • 如果 sum > n，说明当前路径的和已经超过了目标和，直接返回。
  • 如果 path.size() > k，说明已经选择了超过 k 个数字，违反了组合长度的限制，同样直接返回。
• 终止条件：当当前路径的和等于 n 且已选择的数字个数等于 k 时，将当前路径添加到结果列表 ans 中。
• 递归构建：从 startIndex 开始遍历至 9，将当前数字 i 加入路径，然后递归调用 build 方法进行下一层搜索，之后通过 path.removeLast() 回溯，移除刚刚加入的数字，尝试下一个数字。

剪枝策略说明

原注释中提到的剪枝条件 i <= 9 - (k - path.size()) + 1; 与代码中采用的剪枝条件 if (path.size() > k) return; 实现了相同的功能，但后者更直观易懂。它确保了在任何时候路径中的数字数量都不会超过所需组合的长度 k，从而避免了无效的搜索，保证了算法效率。两种剪枝策略在执行效率上基本一致，但后者在代码可读性上更优。

17. 电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

方法一：回溯

class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> combinations = new ArrayList<String>();
        if (digits.length() == 0) {
            return combinations;
        }
        Map<Character, String> phoneMap = new HashMap<Character, String>() {{
            put('2', "abc");
            put('3', "def");
            put('4', "ghi");
            put('5', "jkl");
            put('6', "mno");
            put('7', "pqrs");
            put('8', "tuv");
            put('9', "wxyz");
        }};
        backtrack(combinations, phoneMap, digits, 0, new StringBuffer());
        return combinations;
    }

    public void backtrack(List<String> combinations, Map<Character, String> phoneMap, String digits, int index, StringBuffer combination) {
        if (index == digits.length()) {
            combinations.add(combination.toString());
        } else {
            char digit = digits.charAt(index);
            String letters = phoneMap.get(digit);
            int lettersCount = letters.length();
            for (int i = 0; i < lettersCount; i++) {
                combination.append(letters.charAt(i));
                backtrack(combinations, phoneMap, digits, index + 1, combination);
                combination.deleteCharAt(index);
            }
        }
    }
}

这段代码是一个 Java 程序，实现了一个名为 Solution 的类，该类包含两个方法：letterCombinations 和 backtrack。这个程序的目的是根据给定的电话号码数字字符串（比如 “23”）生成所有可能的字母组合（“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”）。这里，每个数字映射到多个字母（比如 ‘2’ 映射到 “abc”），这些映射关系已经预定义在 phoneMap 中。

方法说明

1. letterCombinations(String digits)

   • 功能：这是主要的接口方法，接收一个字符串 digits 作为输入，返回一个包含所有可能字母组合的列表。
   • 逻辑：首先检查输入字符串是否为空，若为空则直接返回一个空列表。接着，定义了一个哈希映射 phoneMap，将数字字符映射到对应的字母字符串。然后，调用 backtrack 方法进行回溯操作生成所有组合，并将结果收集到 combinations 列表中。

2. backtrack(List combinations, Map phoneMap, String digits, int index, StringBuffer combination)

   • 功能：递归回溯方法，用于生成所有可能的字母组合。
   • 参数：
     • combinations: 存储所有组合的列表。
     • phoneMap: 数字到字母的映射。
     • digits: 输入的数字字符串。
     • index: 当前处理的 digits 中字符的索引。
     • combination: 当前正在构建的组合的缓冲区。
   • 逻辑：
     • 基准情况：如果 index 等于 digits 的长度，说明已经完成一个组合，将其添加到 combinations 列表中。
     • 递归情况：根据当前 index 所对应的数字从 phoneMap 获取对应字母串，遍历这个字母串中的每个字母，将其添加到 combination 中，然后递归调用自身处理下一个数字。在递归返回后，通过 deleteCharAt 方法回溯，移除刚添加的字母，尝试下一个字母。

示例解析

例如，当输入 “23” 时，首先映射 ‘2’ 到 “abc”，然后 ‘3’ 到 “def”。程序会从 “2” 开始，对 “abc” 中的每个字母与 “def” 中的每个字母进行组合，最终生成所有可能的字母组合并返回。

这种方法利用回溯算法有效地减少了重复计算，保证了所有组合都被遍历且只被生成一次，适合解决此类组合问题。