谁做的怀来吧网站,最新的军事新闻,腾讯云网站建设流程,皮肤科在线咨询医生免费咨询216.组合总和III
找出所有相加之和为 n 的 k 个数的组合#xff0c;且满足下列条件#xff1a;
只使用数字1到9 每个数字 最多使用一次 返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次#xff0c;组合可以以任何顺序返回。
示例 1:
输入: k 3, n 7 输…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 {ListInteger temp new ArrayListInteger();ListListInteger ans new ArrayListListInteger();public ListListInteger combinationSum3(int k, int n) {for (int mask 0; mask (1 9); mask) {if (check(mask, k, n)) {ans.add(new ArrayListInteger(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一个 ListInteger用于临时存储当前组合。ans一个 ListListInteger用于存储所有满足条件的组合。
方法
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 {ListInteger temp new ArrayListInteger();ListListInteger ans new ArrayListListInteger();public ListListInteger 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 ArrayListInteger(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 {LinkedListInteger path new LinkedList();ListListInteger ans new ArrayList();public ListListInteger 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 作为路径的存储结构以更直观地展示组合构建过程并在剪枝策略上做了调整。下面是详细的解析
类成员变量
LinkedListInteger path用于保存当前搜索路径上的数字组合。ListListInteger 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 ListString letterCombinations(String digits) {ListString combinations new ArrayListString();if (digits.length() 0) {return combinations;}MapCharacter, String phoneMap new HashMapCharacter, 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(ListString combinations, MapCharacter, 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 中。
方法说明 letterCombinations(String digits) 功能这是主要的接口方法接收一个字符串 digits 作为输入返回一个包含所有可能字母组合的列表。逻辑首先检查输入字符串是否为空若为空则直接返回一个空列表。接着定义了一个哈希映射 phoneMap将数字字符映射到对应的字母字符串。然后调用 backtrack 方法进行回溯操作生成所有组合并将结果收集到 combinations 列表中。 backtrack(List combinations, MapCharacter, String 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” 中的每个字母进行组合最终生成所有可能的字母组合并返回。
这种方法利用回溯算法有效地减少了重复计算保证了所有组合都被遍历且只被生成一次适合解决此类组合问题。
