給定一個無重復(fù)元素的數(shù)組?candidates?和一個目標(biāo)數(shù)?target?，找出?candidates?中所有可以使數(shù)字和為?target?的組合。

candidates?中的數(shù)字可以無限制重復(fù)被選取。

說明：

• 所有數(shù)字（包括?target）都是正整數(shù)。
• 解集不能包含重復(fù)的組合。?

示例?1:

輸入: candidates = [2,3,6,7], target = 7, 所求解集為: [ [7], [2,2,3] ]

示例?2:

輸入: candidates = [2,3,5], target = 8, 所求解集為: [ ? [2,2,2,2], ? [2,3,3], ? [3,5] ]

?

先排序，后剪枝，避免重復(fù)。

這類問題解決重復(fù)的操作一般是先進(jìn)行排序。

?

?

bool cmp1(int x, int y) {return x < y; }class Solution { public:vector<vector<int> > res;vector<vector<int> > combinationSum(vector<int>& candidates, int target){int len = candidates.size();sort(candidates.begin(), candidates.end(), cmp1);vector<int> temp;DFS(candidates, target, temp, 0);return res;}void DFS(vector<int> candidates, int val, vector<int> &v, int cnt){if(val == 0){res.push_back(v);return;}for(int i = cnt; i < candidates.size(); i++){if(candidates[i] <= val){v.push_back(candidates[i]);DFS(candidates, val - candidates[i], v, i);v.pop_back();}}} };

轉(zhuǎn)載于:https://www.cnblogs.com/lMonster81/p/10433878.html

總結(jié)

以上是生活随笔為你收集整理的Leetcode39.Combination Sum组合总和的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。