目錄
力扣39. 組合總和
解析代碼1
解析代碼2
力扣39. 組合總和
39. 組合總和
LCR 081. 組合總和
難度 中等
給你一個(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 輸出: []
提示：
1 <= candidates.length <= 302 <= candidates[i] <= 40-
candidates?的所有元素?互不相同 1 <= target <= 40
class Solution {
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
}
};解析代碼1
因此在選擇當(dāng)前元素并向下傳遞下標(biāo)時(shí)，應(yīng)該直接傳遞當(dāng)前元素下標(biāo)。
此題算是組合總和1，后面還有組合總和2、3、4，可以自己完成。
????????candidates 的所有元素互不相同，因此我們?cè)谶f歸狀態(tài)時(shí)只需要對(duì)每個(gè)元素進(jìn)行如下判斷：
- 跳過(guò)，對(duì)下一個(gè)元素進(jìn)行判斷；
- 將其添加至當(dāng)前狀態(tài)中，我們?cè)谶x擇添加當(dāng)前元素時(shí)，之后仍可以繼續(xù)選擇當(dāng)前元素（可以重復(fù)選擇同一元素）。
因此在選擇當(dāng)前元素并向下傳遞下標(biāo)時(shí)，應(yīng)該直接傳遞當(dāng)前元素下標(biāo)。
class Solution {
int _target;
vector<int> path;
vector<vector<int>> ret;
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
_target = target;
dfs(candidates, 0, 0);
return ret;
}
void dfs(vector<int>& candidates, int pos, int sum)
{
if(sum > _target)
return;
if(sum == _target)
{
ret.push_back(path);
return;
}
for(int i = pos; i < candidates.size(); ++i)
{
path.push_back(candidates[i]);
dfs(candidates, i, sum + candidates[i]);
path.pop_back();
}
}
};
解析代碼2
還可以換一個(gè)思路：如
示例?1：
輸入: candidates = [2,3,6,7], target = 7 輸出: [[7],[2,2,3]]
從選0個(gè)2開(kāi)始，選1、2、3、4...個(gè)2，直到sum >= target。
然后在上面選2的個(gè)數(shù)的基礎(chǔ)上開(kāi)始選3...，直到選完數(shù)組的數(shù)。所有情況枚舉完再恢復(fù)現(xiàn)場(chǎng)。文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-861035.html
class Solution {
int _target;
vector<int> path;
vector<vector<int>> ret;
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
_target = target;
dfs(candidates, 0, 0);
return ret;
}
void dfs(vector<int>& candidates, int pos, int sum)
{
if(sum == _target)
{
ret.push_back(path);
return;
}
if(sum > _target || pos == candidates.size()) // 下面沒(méi)判斷pos這就要判斷
return;
for (int k = 0; k * candidates[pos] + sum <= _target; ++k) // 枚舉個(gè)數(shù)
{
if (k != 0)
path.push_back(candidates[pos]);
dfs(candidates, pos + 1, sum + k * candidates[pos]);
}
for (int k = 1; k * candidates[pos] + sum <= _target; ++k) // 恢復(fù)現(xiàn)場(chǎng)
{
path.pop_back();
}
}
};
文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-861035.html
到了這里，關(guān)于每日OJ題_DFS回溯剪枝⑨_力扣39. 組合總和（兩種思路）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
