前引：明天就考最后一趟考試，最近考試周，我時時斷更，從明天開始，就會一直更新了，可以期待一下

解題思路：

? ? ? ? 1.獲取信息：

? ? ? ? ? ? ? ? 給定一個無重復的整數數組和一個目標值

? ? ? ? ? ? ? ? 從數組中選取任意數量的數字，使它們的和等于目標值，就是一組滿足條件的組合

? ? ? ? ? ? ? ? 要找出所有不同的組合，并按任意順序返回它們

? ? ? ? ? ? ? ? 注：同一個數字可以無限制重復被選取

? ? ? ? ? ? ? ?額外信息：1?<= candidates.length <= 30? ?

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?2 <=candidates[ i ] <= 40?

????????2.分析題目：

? ? ? ? ? ? ? ? 不同于之前類似的題目，這次，同一個數字可以無限制重復被選取，就需要你推陳出新了

? ? ? ? ? ? ? ? 由于可以選任意數量的數字為一組，所以，面對可能出現很多種情況的條件下

? ? ? ? ? ? ? ? 我打算使用回溯法，不了解回溯法，可以去看一下38題的題解，有詳細講解哦

? ? ? ? ? ? ? ? 這里你可以思考一下，回溯法該怎么實現，我會在最后一個環節借著代碼來講解我的思路的

? ? ? ? 3.示例查驗：

? ? ? ? ? ? ? ? 你可以檢驗一下自己的思路是否正確

? ? ? ? 4.嘗試編寫代碼：

? ? ? ? ? ? ? ? （1）回溯法

? ? ? ? ? ? ? ? ? ? ? ? 思路：每次從數組種選取一個數，進入下層遞歸，終止條件是滿足所有數字的和為目標值

? ? ? ? ? ? ? ? ? ? ? ? 其實我本來想詳細說說我的思路的，但是明天早上，我就要考試了，所以我打算長話短說，委屈你了，你可以看我的代碼及其注釋來進行理解哦

class Solution {
public:vector<vector<int>> combinationSum(vector<int>& candidates, int target) {sort(candidates.begin(),candidates.end());//數組按從小到大的順序排列vector<vector<int>>res;//儲存結果的容器vector<int>path;//儲存每次選取的數字reBack(res,candidates,target,path,0);進入回溯return res;//返回結果}
private:void reBack(vector<vector<int>>&res,vector<int>&candidates,int les,vector<int>&path,int i){if(les==0){//如果選取的所有數字之和等于目標值res.push_back(path);return;}for(int j=i;j<candidates.size();j++){//每次選取數字if(candidates[j]>les)return;//剪枝，如果數字大于目標數的大小，就返回path.push_back(candidates[j]);//選取數字reBack(res,candidates,les-candidates[j],path,j);//進入下層遞歸path.pop_back();//移除選取的數字}}
};

? ? ? ? ? ? ? ? （2）優化哦

? ? ? ? ? ? ? ? ? ? ? ? 這次，不負眾望，帶來了優化及優化思路哦

? ? ? ? ? ? ? ? ? ? ? ? 優化思路：上面的方法，主要的浪費是在每次選取數字的時候，會進行比較多的無用操作，所以，有沒有辦法避免呢？

? ? ? ? ? ? ? ? ? ? ? ? 當然可以了，我們需要對原數組進行預先的處理，因為數組中的數字最大也就40，數組中的數字的數目最多也就30個

? ? ? ? ? ? ? ? ? ? ? ? 所以，你還是看我的代碼及注釋吧，最近我比較懶惰

class Solution {
public:vector<vector<int>> combinationSum(vector<int>& candidates, int target) {vector<bool>cand(41,false);//對數組進行預處理for(int&c:candidates){cand[c]=true;}vector<int>path;//儲存選取的數字vector<vector<int>>res;//儲存結果的容器reBack(cand,path,res,target,2);//進入回溯return res;//返回結果}
private:void reBack(vector<bool>&cand,vector<int>&path,vector<vector<int>>&res,int les,int i){if(les==0){//如果選取的數字之和等于目標值res.push_back(path);return;}for(i;i<=les;i++){//數字選取的范圍，有效地進行了剪枝操作if(cand[i]){//如果該數字存在path.push_back(i);//選取該數字reBack(cand,path,res,les-i,i);path.pop_back();}}}
};

本次題解就到這里了，希望不掛科吧，每次發帖子感覺就像在跟一個讓我很舒服的人交流，這幾天沒有交流，反而感覺患得患失的，盡量每日一更，每天都來與你交流一下

還是提一嘴，紙上得來終覺淺，絕知此事要躬行哦

祝要考期末的，都不掛科，哈哈