216.組合總和III

找出所有相加之和為 n 的 k 個數(shù)的組合，且滿足下列條件：

只使用數(shù)字1到9
每個數(shù)字 最多使用一次
返回 所有可能的有效組合的列表 。該列表不能包含相同的組合兩次，組合可以以任何順序返回。

示例 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
沒有其他符合的組合了。

方法一：二進(jìn)制（子集）枚舉

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 個數(shù)字組成的序列，這些數(shù)字取自 1 到 9 之間的整數(shù)，每個數(shù)字最多使用一次。這是一種使用位操作優(yōu)化的組合求解方法。

成員變量

與之前一樣，定義了兩個成員變量：

• temp：一個 List<Integer>，用于臨時存儲當(dāng)前組合。
• ans：一個 List<List<Integer>>，用于存儲所有滿足條件的組合。

方法

combinationSum3(int k, int n)

• 功能：主方法，接收目標(biāo)和 n 和組合長度 k 作為參數(shù)，返回所有符合條件的組合。
• 過程：通過遍歷從 0 到 (1 << 9)（即 2^9）之間所有可能的掩碼值（mask），利用 check 方法驗(yàn)證每個掩碼是否代表一個有效的組合。如果是，則將該組合添加到答案列表 ans 中。

check(int mask, int k, int n)

• 功能：輔助方法，檢查給定的掩碼 mask 是否代表一個有效的組合，即組合中的數(shù)字個數(shù)是否為 k 且這些數(shù)字之和為 n。
• 參數(shù)：除了掩碼 mask 外，還接收組合長度 k 和目標(biāo)和 n。
• 過程：
  • 首先清空 temp，然后遍歷從 0 到 8（代表數(shù)字 1 到 9），如果某位在 mask 中被設(shè)置（即該位為 1），則將對應(yīng)的數(shù)字（i + 1）添加到 temp 中。
  • 檢查 temp 的大小是否等于 k，如果不等直接返回 false。
  • 計算 temp 中所有數(shù)字的和，判斷這個和是否等于 n，如果相等返回 true，否則返回 false。

這種方法利用位運(yùn)算高效地枚舉了所有可能的選擇情況，相比于之前的遞歸解法，此方法在某些情況下可以減少遞歸調(diào)用的開銷，尤其是在處理較大范圍的組合問題時更為高效。

方法二：組合枚舉

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的類，該類包含方法來找出所有組合之和等于特定目標(biāo)值n的k個不同正整數(shù)的組合，且這些整數(shù)都在1到n之間（這里限制為1到9，因?yàn)轭}目隱含了這個范圍，如dfs函數(shù)的第二個參數(shù)所示）。這是一個經(jīng)典的回溯算法應(yīng)用實(shí)例。

方法說明

• combinationSum3(int k, int n): 這是主要的方法，接收兩個整數(shù)參數(shù)k和n，分別代表需要找到的組合的元素個數(shù)以及這些元素的和。它初始化調(diào)用深度優(yōu)先搜索(dfs)方法來尋找所有符合條件的組合，并返回存儲這些組合的二維列表ans。

• dfs(int cur, int n, int k, int sum): 這是一個遞歸輔助函數(shù)，用于執(zhí)行深度優(yōu)先搜索。

  • cur表示當(dāng)前考慮加入組合的起始數(shù)字（遞增的基礎(chǔ)）。
  • n是可選數(shù)字的最大值，在這個上下文中固定為9。
  • k和sum與主方法接收的參數(shù)相同，分別代表需要的組合長度和目標(biāo)和。

  該函數(shù)的工作原理如下：

  • 剪枝：首先判斷當(dāng)前路徑是否有可能達(dá)到解。如果當(dāng)前臨時組合的長度加上剩余數(shù)字的數(shù)量小于k，或者已經(jīng)超過k，直接返回，無需繼續(xù)搜索。
  • 結(jié)束條件：當(dāng)臨時組合的長度等于k時，檢查這些數(shù)字的和是否等于目標(biāo)sum。如果是，則將當(dāng)前組合添加到答案列表中，并返回。
  • 遞歸搜索：嘗試選擇當(dāng)前數(shù)字cur，將其加入臨時組合temp，然后遞歸調(diào)用dfs函數(shù)嘗試下一個數(shù)字。之后通過temp.remove(temp.size() - 1)撤銷選擇（回溯），再嘗試不包含當(dāng)前數(shù)字的情況。

示例解析

假設(shè)調(diào)用combinationSum3(3, 7)，該函數(shù)將尋找所有和為7且包含3個數(shù)字的組合，這些數(shù)字來自1到9。可能的結(jié)果包括[1, 2, 4]。此過程通過深度優(yōu)先搜索逐層嘗試每一種可能的組合，并通過剪枝策略減少無效的搜索路徑，從而高效地找到所有解。

方法三：回溯

// 上面剪枝 i <= 9 - (k - path.size()) + 1; 如果還是不清楚
// 也可以改為 if (path.size() > k) return; 執(zhí)行效率上是一樣的
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 個不同數(shù)字的組合的問題，其中數(shù)字選擇范圍限定在 1 到 9 之間。與之前版本相比，這段代碼采用了一些小的改動和優(yōu)化，使用了 LinkedList 作為路徑的存儲結(jié)構(gòu)，以更直觀地展示組合構(gòu)建過程，并在剪枝策略上做了調(diào)整。下面是詳細(xì)的解析：

類成員變量

• LinkedList<Integer> path：用于保存當(dāng)前搜索路徑上的數(shù)字組合。
• List<List<Integer>> ans：用于存儲所有滿足條件的組合。

主方法 combinationSum3(int k, int n)

• 功能：接收目標(biāo)和 n 和組合長度 k 作為參數(shù)，調(diào)用 build 方法生成所有符合條件的組合，最后返回所有組合的列表 ans。

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

• 功能：遞歸構(gòu)建組合。接收當(dāng)前需要的組合長度 k、目標(biāo)和 n、搜索起始數(shù)字 startIndex 以及當(dāng)前路徑和 sum 作為參數(shù)。
• 剪枝條件：
  • 如果 sum > n，說明當(dāng)前路徑的和已經(jīng)超過了目標(biāo)和，直接返回。
  • 如果 path.size() > k，說明已經(jīng)選擇了超過 k 個數(shù)字，違反了組合長度的限制，同樣直接返回。
• 終止條件：當(dāng)當(dāng)前路徑的和等于 n 且已選擇的數(shù)字個數(shù)等于 k 時，將當(dāng)前路徑添加到結(jié)果列表 ans 中。
• 遞歸構(gòu)建：從 startIndex 開始遍歷至 9，將當(dāng)前數(shù)字 i 加入路徑，然后遞歸調(diào)用 build 方法進(jìn)行下一層搜索，之后通過 path.removeLast() 回溯，移除剛剛加入的數(shù)字，嘗試下一個數(shù)字。

剪枝策略說明

原注釋中提到的剪枝條件 i <= 9 - (k - path.size()) + 1; 與代碼中采用的剪枝條件 if (path.size() > k) return; 實(shí)現(xiàn)了相同的功能，但后者更直觀易懂。它確保了在任何時候路徑中的數(shù)字?jǐn)?shù)量都不會超過所需組合的長度 k，從而避免了無效的搜索，保證了算法效率。兩種剪枝策略在執(zhí)行效率上基本一致，但后者在代碼可讀性上更優(yōu)。

17. 電話號碼的字母組合

給定一個僅包含數(shù)字 2-9 的字符串，返回所有它能表示的字母組合。答案可以按 任意順序 返回。

給出數(shù)字到字母的映射如下（與電話按鍵相同）。注意 1 不對應(yīng)任何字母。

方法一：回溯

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 程序，實(shí)現(xiàn)了一個名為 Solution 的類，該類包含兩個方法：letterCombinations 和 backtrack。這個程序的目的是根據(jù)給定的電話號碼數(shù)字字符串（比如 “23”）生成所有可能的字母組合（“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”）。這里，每個數(shù)字映射到多個字母（比如 ‘2’ 映射到 “abc”），這些映射關(guān)系已經(jīng)預(yù)定義在 phoneMap 中。

方法說明

1. letterCombinations(String digits)

   • 功能：這是主要的接口方法，接收一個字符串 digits 作為輸入，返回一個包含所有可能字母組合的列表。
   • 邏輯：首先檢查輸入字符串是否為空，若為空則直接返回一個空列表。接著，定義了一個哈希映射 phoneMap，將數(shù)字字符映射到對應(yīng)的字母字符串。然后，調(diào)用 backtrack 方法進(jìn)行回溯操作生成所有組合，并將結(jié)果收集到 combinations 列表中。

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

   • 功能：遞歸回溯方法，用于生成所有可能的字母組合。
   • 參數(shù)：
     • combinations: 存儲所有組合的列表。
     • phoneMap: 數(shù)字到字母的映射。
     • digits: 輸入的數(shù)字字符串。
     • index: 當(dāng)前處理的 digits 中字符的索引。
     • combination: 當(dāng)前正在構(gòu)建的組合的緩沖區(qū)。
   • 邏輯：
     • 基準(zhǔn)情況：如果 index 等于 digits 的長度，說明已經(jīng)完成一個組合，將其添加到 combinations 列表中。
     • 遞歸情況：根據(jù)當(dāng)前 index 所對應(yīng)的數(shù)字從 phoneMap 獲取對應(yīng)字母串，遍歷這個字母串中的每個字母，將其添加到 combination 中，然后遞歸調(diào)用自身處理下一個數(shù)字。在遞歸返回后，通過 deleteCharAt 方法回溯，移除剛添加的字母，嘗試下一個字母。

示例解析

例如，當(dāng)輸入 “23” 時，首先映射 ‘2’ 到 “abc”，然后 ‘3’ 到 “def”。程序會從 “2” 開始，對 “abc” 中的每個字母與 “def” 中的每個字母進(jìn)行組合，最終生成所有可能的字母組合并返回。

這種方法利用回溯算法有效地減少了重復(fù)計算，保證了所有組合都被遍歷且只被生成一次，適合解決此類組合問題。