#Java #回溯 #組合問題

開源學習資料

Feeling and experiences：

組合總和III：力扣題目鏈接

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

• 只使用數字1到9
• 每個數字?最多使用一次?

返回 所有可能的有效組合的列表 。該列表不能包含相同的組合兩次，組合可以以任何順序返回。

該題與之前做的組合很類似，相當于就在組合的基礎上，多了一個三數之和 == 目標值。

回溯思路相同，只需要改一些細節即可：

class Solution {//創建存放結果的集合List<List<Integer>> ans = new ArrayList<>();//創建 path 集合 ，記錄每一次組合結果List<Integer> path = new LinkedList<>();public List<List<Integer>> combinationSum3(int k, int n) {
getCombinationSum(k,n,0,1);
return ans;}public void getCombinationSum(int k , int target,int sum ,int startIndex){//回溯三部曲，確定遞歸函數參數 k , n ,startIndex//這里 n 就相當于目標值 targetif(path.size() == k){if(sum == target){//如果和等于目標值了，則把這一組數據加入到結果集中ans.add(new ArrayList(path));return;}}for(int i = startIndex;i<=9;i++){sum+=i;path.addLast(i);getCombinationSum(k,target,sum,i+1);//回溯：sum-=i;path.removeLast();}}
}

這里的細節與關鍵有：

for循環的 i 不是從1開始了，而是 i = startIndex；

多了一個sum需要進行回溯；

題目要求（從1~9中進行選擇，同樣不能選擇兩個相同的數）；

結合之前的組合問題，深刻體會一下回溯算法：

1. 遞歸的終止條件:
? 當?path?的大小等于?k?時，檢查?sum?是否等于?target。如果是，將當前路徑添加到結果集?ans。
? 這里之所以不把?if(sum?==?target)?條件直接放在?for?循環內部，是因為我們只想在找到?k?個數字的組合時才檢查它們的和是否等于?target。如果提前放在循環內，那么即使組合中數字個數不足?k?個，也會進行檢查，這與題目要求不符。

2. for?循環:
? 這個循環是用來遍歷所有可能的數字組合。
? i?從?startIndex?開始，這是為了避免重復。每次遞歸調用?getCombinationSum?時，都會增加?startIndex，這樣就不會重復考慮之前的數字，保證了組合的唯一性。

3. 遞歸調用:
? 在?for?循環中，對每個數字?i，將其加入到?path?中，并更新?sum。
? 然后遞歸調用?getCombinationSum，探索包含當前數字的所有可能組合。

4. 回溯:
? 在遞歸返回后，需要撤銷之前的選擇（即從?path?中移除?i?并從?sum?中減去?i），以便于?for?循環中的下一次嘗試。
?

電話號碼的字母組合：力扣題目鏈接

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

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

當我看到每個數字有與之對應的字母時，第一時間相當用哈希map，想通過鍵值對匹配來完成。

以下是第一次用HashMap寫出來的答案：

class Solution {//創建一個結果集，存放答案List<String> ans = new ArrayList<>();StringBuilder sb = new StringBuilder();public List<String> letterCombinations(String digits) {//判斷digitis，也相當于減枝了if(digits == null || digits.length() == 0){return ans;}//看到字母和數字匹配，想到了哈希map//創建一個hashmapMap<Integer,String> map = new HashMap<>(){{//把對應元素添加到map集合中put(2,"abc");put(3,"def");put(4,"ghi");put(5,"jkl");put(6,"mno");put(7,"pqrs");put(8,"tuv");put(9,"wxyz");}};back(digits,sb,0,map);return ans;}//遞歸方法：public void back(String digits,StringBuilder sb,int index,Map<Integer,String> map){//什么時候把得到的結果放到結果集中？ 觀察得出，輸出的每個字符串，長度等于digits的長度if(sb.length() == digits.length()){ans.add(sb.toString());return;}        //傳入一個digits，會去解析里面的數字int number = Integer.parseInt(String.valueOf(digits.charAt(index)));String value = map.get(number);for(int i =0;i<value.length();i++){sb.append(value.charAt(i));back(digits,sb,index+1,map);//回溯：sb.deleteCharAt(sb.length()-1);}}
}

我基本是按照之前的組合問題的做法來思考的：

? 每一步遞歸都會對一個數字進行處理，將其映射到對應的所有字母，并繼續遞歸處理下一個數字。
? 當構建的字符串長度與輸入?digits?的長度相同時，將其視為一個有效組合，并加入到結果集。
? 通過回溯（移除已添加的最后一個字符），算法能夠撤銷之前的選擇，從而探索所有不同的組合路徑。

?而代碼隨想錄中用的是數組，我認為這樣更優：

class Solution {//設置全局列表存儲最后的結果List<String> list = new ArrayList<>();public List<String> letterCombinations(String digits) {if (digits == null || digits.length() == 0) {return list;}//初始對應所有的數字，為了直接對應2-9，新增了兩個無效的字符串""String[] numString = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};//迭代處理backTracking(digits, numString, 0);return list;}//每次迭代獲取一個字符串，所以會設計大量的字符串拼接，所以這里選擇更為高效的 StringBuildStringBuilder temp = new StringBuilder();//比如digits如果為"23",num 為0，則str表示2對應的 abcpublic void backTracking(String digits, String[] numString, int num) {//遍歷全部一次記錄一次得到的字符串if (num == digits.length()) {list.add(temp.toString());return;}//str 表示當前num對應的字符串String str = numString[digits.charAt(num) - '0'];for (int i = 0; i < str.length(); i++) {temp.append(str.charAt(i));//cbackTracking(digits, numString, num + 1);//剔除末尾的繼續嘗試temp.deleteCharAt(temp.length() - 1);}}
}

大體思路都是相同的！

青山依舊，

韶華幾許~

Fighting！