題目：
鏈接：LeetCode 39. 組合總和
難度：中等
給你一個(gè) 無(wú)重復(fù)元素 的整數(shù)數(shù)組 candidates 和一個(gè)目標(biāo)整數(shù) target ，找出 candidates 中可以使數(shù)字和為目標(biāo)數(shù) target 的 所有 不同組合 ，并以列表形式返回。你可以按 任意順序 返回這些組合。
candidates 中的 同一個(gè) 數(shù)字可以 無(wú)限制重復(fù)被選取 。如果至少一個(gè)數(shù)字的被選數(shù)量不同，則兩種組合是不同的。
對(duì)于給定的輸入，保證和為 target 的不同組合數(shù)少于 150 個(gè)。
示例 1：
輸入：candidates = [2,3,6,7], target = 7
輸出：[[2,2,3],[7]]
解釋：
2 和 3 可以形成一組候選，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一個(gè)候選， 7 = 7 。
僅有這兩種組合。
示例 2：
輸入: candidates = [2,3,5], target = 8
輸出: [[2,2,2,2],[2,3,3],[3,5]]
示例 3：
輸入: candidates = [2], target = 1
輸出: []
提示：文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-627613.html
- 1 <= candidates.length <= 30
- 2 <= candidates[i] <= 40
- candidates 的所有元素 互不相同
- 1 <= target <= 40
回溯+剪枝：
詳細(xì)解析看這篇回溯算法秒殺所有排列/組合/子集問(wèn)題，這類題型通殺。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-627613.html
代碼：
class Solution {
public:
vector<vector<int>> res;
vector<int> track;
int trackSum;
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
trackSum = 0;
backtrack(candidates, 0, target);
return res;
}
void backtrack(vector<int>& candidates, int start, int target) {
if(trackSum == target) {
res.emplace_back(track);
return;
}
else if(trackSum > target) return;
for(int i = start; i < candidates.size(); i++)
{
track.emplace_back(candidates[i]);
trackSum += candidates[i];
backtrack(candidates, i, target); // 元素可復(fù)用，所以繼續(xù)從第i位開(kāi)始遍歷
track.pop_back();
trackSum -= candidates[i];
}
}
};
到了這里，關(guān)于LeetCode 39. 組合總和（回溯+剪枝）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
