[力扣leetcode39]組合總和及回溯法

• 回溯yyds
• 小練習

回溯yyds

在算法優化上面回溯法或許沒有那么引人注意，但是對于一些題目來說能夠回溯已經很好了。

題目：給定一個無重復元素的數組 candidates 和一個目標數 target ，找candidates 中所有可以使數字和為 target 的組合。candidates 中的數字可以無限制重復被選取。
比如輸入：candidates = [2,3,6,7], target = 7,
所求解集為：
[
[7],
[2,2,3]
]

對于這道題目最樸素的解法當然是暴力搜索，但是其實組合類問題一直都是回溯法的天下，可以排除一些沒有必要的驗證。回溯法的本質我個人認為是一個樹，不妨以上述的輸入為例。

第一輪2，3，6，7都可以選，如果第一輪選了2，第二輪可以選2，3，因為必須要滿足每一輪取的數必須大于等于上一輪取的數，這樣可以避免重復，同時不需要取6，7，因為要滿足總和為7。如果第二輪取了2，第三輪可以取2，3，先驗證2，不滿足且不能繼續取了，回溯上一輪再取3，發現滿足題意，即找到一個組合。所以思路就來了，用for循環遍歷元素，再用回溯法。回溯法有個明顯的格式是進棧（或者其他容器）->回溯->出棧。需要額外注意的是startindex的選取，本題每一輪選取的數都要大于等于上一輪的數。

class Solution { private:vector<vector<int>> result;vector<int> path;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();}} public:vector<vector<int>> combinationSum(vector<int>& candidates, int target) {result.clear();path.clear();backtracking(candidates, target, 0, 0);return result;} };

小練習

因為上學期離散學到了球和盒子的問題，比較難的是把不可辨別的球放到不可辨別的盒子里面，典型的就是自然數的組合問題，比如3，可以有1+1+1，1+2，兩種組合方式。這個問題也可以用回溯法解決。

vector<vector<int>> res; vector<int> vec; void back(int n,int cur){int sum=accumulate(vec.begin(),vec.end(),0);if(sum==n){res.push_back(vec);return;}for(int i=cur;i<n;i++){if(i+sum<=n)vec.push_back(i);else return;back(n,i);vec.pop_back();}}int main(){int n=6;back(n,1);for(int i=0;i<res.size();i++){for(int j=0;j<res[i].size();j++){cout<<res[i][j];}cout<<endl;} }

總結

以上是生活随笔為你收集整理的[力扣leetcode39]组合总和及回溯法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。