題目一：組合綜合

問題描述

39. 組合總和 - 力扣（LeetCode）

給你一個?無重復元素?的整數數組?candidates?和一個目標整數?target?，找出?candidates?中可以使數字和為目標數?target?的 所有?不同組合?，并以列表形式返回。你可以按?任意順序?返回這些組合。

candidates?中的?同一個?數字可以?無限制重復被選取?。如果至少一個數字的被選數量不同，則兩種組合是不同的。?

對于給定的輸入，保證和為?target?的不同組合數少于?150?個。

示例?1：

輸入：candidates = [2,3,6,7], target = 7
輸出：[[2,2,3],[7]]
解釋：
2 和 3 可以形成一組候選，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一個候選， 7 = 7 。
僅有這兩種組合。

解題步驟

這一題是在組合總和③上有了進一步的改進和要求

我們依舊可以用回溯三部曲模板解決

1.確定函數返回值及參數

這里我們需要從candidates數組中取值，所以這個數組應該一直陪伴我們，加入參數列表！

相當于我們之前從1~n中取值的n，都表示我們的取值范圍

同理，我們需要一直參考target數值，所以它也是參數的一員

為了記錄每個組合的總和，我們需要一個新變量用于存儲，隨之改變，所以加入新變量sum

最后仍然是我的開始索引，防止重復

void backtracking(vector<int>& candidates,int target,int sum,int startindex)

?2.確定終止條件

終止條件就是說我們找到答案會出現的情況，或者已知明確不可能出現答案就不要繼續的情況

所以分開判斷

if(sum>target){

? ? ? ? return;

}

if(sum==target){

? ? ? ? result.push_back(path);

? ? ? ? return;

}

3.單層搜索邏輯

使用for循環，遍歷candidates數組中的每一個數字，

在每一層中我們需要往path中加入該數字

同時計算sum值

然后遞歸的使用backtracking函數，獲得每一種可能情況

再進行回溯操作，sum值減去加入的數字值，數字也從path中pop_back

for(int i=startindex;i<candidates.size();i++){

? ? ? ? sum+=candidates[i];

? ? ? ? path.push_back(candidates[i]);

? ? ? ? backtracking(candidates,target,sum,startindex);//由于可以重復使用數字，所以此處startindex不需要+1

? ? ? ? sum-=candidates[i];

? ? ? ? path.pop_back();

}

最后只需要整合一下這個回溯函數，在主函數中正確傳參調用即可！

完整代碼如下！?

code

class Solution {
public:vector<int> path;vector<vector<int>> result;void backtracking(vector<int>& candidates,int target,int sum,int startindex){if(sum>target){return;}if(sum==target){result.push_back(path);return;}for(int i=startindex;i<candidates.size();i++){sum+=candidates[i];path.push_back(candidates[i]);backtracking(candidates,target,sum,i);sum-=candidates[i];path.pop_back();}}vector<vector<int>> combinationSum(vector<int>& candidates, int target) {backtracking(candidates,target,0,0);return result;}
};

---

題目二：電話號碼的字母組合

問題描述

17. 電話號碼的字母組合 - 力扣（LeetCode）

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

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

示例 1：

輸入：digits = "23"
輸出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

示例 2：

輸入：digits = ""
輸出：[]

示例 3：

輸入：digits = "2"
輸出：["a","b","c"]

解題步驟

想必縮寫對應數字這事大家肯定很熟悉了

（在背后說人家壞話或者講機密時就用數字代號的事沒少干ψ(｀?′)ψ

那么這一題相較于之前的組合題區別就在于，它的選值對象不再是同一個范圍內的數字了

而是存在數字對應字符串，在字符串中選取對應值，

并且這一題的組合長度也是固定的，給定dights有幾位，我們的組合長度就是幾位

簡單分析就是這樣，那當務之急就是解決數字對應字符串

這樣才可以確定之后的取值范圍

關于映射關系，我們可以選用數組和map

這里選擇二維數組

const string lettermap[10]{

? ? ? ? "","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"

? ? };

?0號和1號位為空，雖然看似一維數組，但由于string可以按照數組使用，所以是二維滴！

同樣，我們需要一個存儲過程量和一個存儲最后結果集的變量，

根據題目所求的數據類型，定義為👇

string s;//過程量，存儲每一種可能

vector<string> result;//結果集，存放所有正確結果

ok，準備完畢，開始走回溯三部曲

1.確定函數返回值及參數

這里我們不能一味的拿來之前的參數列表使用，一定要明確參數的意義

當然返回值依然是void

要把數字轉化為對應字母，那我們就需要該數字，和取到哪一位數字的一個標識

可以這么想，我們的函數需要遞歸調用的，每次都需要看取哪一位元素，

所以digits用來看，index用來指并且是要動態改變的

void backtracking(const string& digits,int index)?

?2.終止條件

既然我們已經派出index指向我們所挑選的數字

那么只要index的數值等于digits的大小，那就意味著指到最后一位了，完成我們的任務了！

所以滿足終止條件，我們需要加入這個s到結果集中并返回

if(index==digits.size()){

? ? ? ? result.push_back(s);

? ? ? ? return;

}

?3.單層遍歷邏輯

我們需要遍歷的是當前數字所對應的字符串（或者說字符數組）

所以在執行遍歷之前，我們應該取出這個字符數組

取出字符數組又分為兩步

1).確認當前數字

2).找數字對應字符數組

int digit=digits[index]-'0';//digits為字符串類型，取出類型需要通過-'0'轉為int型

string letters=lettermap[digit];//在我們的對應二維數組中找到對應string

?ok萬事大吉，開始進入單層遍歷邏輯

為方便理解我們用digits = "23"來舉例，最開始肯定是拿到2對應的字符串“abc”嘛

那就遍歷這個字符串for(int i=0;i<letters.size();i++)

在這個循環里，把單個字符串加入到s中，第一個加入的是"a"

然后遞歸調用backtracking函數，我們就可以拿到3對應的字符串“def”

然后再遍歷“def”，分別與a進行組合，得到三個組合，a這個結點就組合完畢

最外層就可以再指向下一個b，再與def進行同樣的組合

過程類似下圖，只舉例了第一個a的情況

?那么我們的單層遍歷代碼如下：

for(int i=0;i<letters.size();i++){

? ? ? ? s.push_back(letters[i]);

? ? ? ? backtracking(digits,index+1);

? ? ? ? s.pop_back();

}

整合所有代碼， 在主函數中調用即可

這里呢我們可以做一個剪枝操作，

如果給我們的數字序列為空，那么直接返回result（初始為空）即可

if(digits.size()==0){

? ? ? ? return result;

}

code

class Solution {
public:string s;vector<string> result;const string lettermap[10]{"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};void backtracking(const string& digits,int index){if(index==digits.size()){result.push_back(s);return;}int dight=digits[index]-'0';string letters=lettermap[dight];for(int i=0;i<letters.size();i++){s.push_back(letters[i]);backtracking(digits,index+1);s.pop_back();}}vector<string> letterCombinations(string digits) {if(digits.size()==0){return result;}backtracking(digits,0);return result;}
};

補充：

const 是 constant 的縮寫，本意是不變的，不易改變的意思。在 C++ 中是用來修飾內置類型變量，自定義對象，成員函數，返回值，函數參數。

C++ const 允許指定一個語義約束，編譯器會強制實施這個約束，允許程序員告訴編譯器某值是保持不變的。如果在編程中確實有某個值保持不變，就應該明確使用const，這樣可以獲得編譯器的幫助。

---

題目三：組合總和②

問題描述

40. 組合總和 II - 力扣（LeetCode）

給定一個候選人編號的集合?candidates?和一個目標數?target?，找出?candidates?中所有可以使數字和為?target?的組合。

candidates?中的每個數字在每個組合中只能使用?一次?。

注意：解集不能包含重復的組合。?

示例?1:

輸入: candidates =?[10,1,2,7,6,1,5], target =?8,
輸出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

示例?2:

輸入: candidates =?[2,5,2,1,2], target =?5,
輸出:
[
[1,2,2],
[5]
]

解題步驟

不知道有沒有和我一樣的小蠢蛋，看到這一題沒仔細審題還以為是之前做過沒有提交

嘎嘎寫完代碼運行完才發現不對勁

這一題的特殊之處在于它所給的candidates是可能重復的，但最后要求解集中不能包含重復的

那么按照之前的邏輯，我們只能滿足它在各不相同的情況下不重復，

但不能解決同一個取值空間中有相同元素的重復可能

所以這里我們要加入一個新的操作——去重

其它代碼都大致相同就不多解釋，重點來理一下去重的邏輯

我們需要在每一層去確認當前元素之前是否被使用過，

那么為了方便對比前后，可以先將整個candidates數組進行排序，

那相同值肯定就出現在旁邊，不需要考慮是多久之前出現

sort(candidates.begin(), candidates.end());

同時需要留下記錄，所以需要一個新的數組來存儲這些記錄

vector<bool> used(candidates.size(), false);//初始化為false全部沒用過

那么這個used數組應該要伴隨這組結果一直遞歸才能查看情況

所以把他加入參數列表

? ? void backtracking(vector<int>& candidates,int target,int sum,int index,vector<bool>& used){

那么在單層遍歷中需要同時改變這個結點的使用狀態

????????????sum+=candidates[i];

? ? ? ? ? ? path.push_back(candidates[i]);

? ? ? ? ? ? used[i]=true;

? ? ? ? ? ? backtracking(candidates,target,sum,i+1,used);

? ? ? ? ? ? used[i]=false;

? ? ? ? ? ? sum-=candidates[i];

? ? ? ? ? ? path.pop_back();

簡單的已經鋪墊完了，接下來捋一下去重方法

重復那就是candidates[i] == candidates[i - 1]，但是只加這一個條件會使我們失去確實用到兩個相同元素的結果，而不是僅去掉重復的結果（細品這個差別）

所以還需要加上used[i - 1] == false代表對于同一樹層candidates[i - 1]使用過（因為回溯所以false）

在滿足這兩個條件下我們就需要continue跳過這個組合結果

if (i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == false) {

? ? ? ? ? ? ? ? continue;

? ? ? ? ? ? }

完整代碼如下！?

code

class Solution {
public:vector<int> path;vector<vector<int>> result;int sum;void backtracking(vector<int>& candidates,int target,int sum,int index,vector<bool>& used){if(sum>target){return;}if(sum==target){result.push_back(path);return;}for(int i=index;i<candidates.size();i++){if (i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == false) {continue;}sum+=candidates[i];path.push_back(candidates[i]);used[i]=true;backtracking(candidates,target,sum,i+1,used);used[i]=false;sum-=candidates[i];path.pop_back();}}vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {vector<bool> used(candidates.size(), false);path.clear();result.clear();sort(candidates.begin(), candidates.end());backtracking(candidates,target,0,0,used);return result;}
};