代碼隨想錄-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<Integer>，用于臨時存儲當前組合。
ans：一個 List<List<Integer>>，用于存儲所有滿足條件的組合。

方法

`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<Integer> path：用于保存當前搜索路徑上的數字組合。
List<List<Integer>> 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 中。

方法說明

letterCombinations(String digits)
- 功能：這是主要的接口方法，接收一個字符串 digits 作為輸入，返回一個包含所有可能字母組合的列表。
- 邏輯：首先檢查輸入字符串是否為空，若為空則直接返回一個空列表。接著，定義了一個哈希映射 phoneMap，將數字字符映射到對應的字母字符串。然后，調用 backtrack 方法進行回溯操作生成所有組合，并將結果收集到 combinations 列表中。
backtrack(List combinations, Map<Character, String> phoneMap, String digits, int index, StringBuffer combination)
- 功能：遞歸回溯方法，用于生成所有可能的字母組合。
- 參數：
  - combinations: 存儲所有組合的列表。
  - phoneMap: 數字到字母的映射。
  - digits: 輸入的數字字符串。
  - index: 當前處理的 digits 中字符的索引。
  - combination: 當前正在構建的組合的緩沖區。
- 邏輯：
  - 基準情況：如果 index 等于 digits 的長度，說明已經完成一個組合，將其添加到 combinations 列表中。
  - 遞歸情況：根據當前 index 所對應的數字從 phoneMap 獲取對應字母串，遍歷這個字母串中的每個字母，將其添加到 combination 中，然后遞歸調用自身處理下一個數字。在遞歸返回后，通過 deleteCharAt 方法回溯，移除剛添加的字母，嘗試下一個字母。