題目:
Given a set of candidate numbers ( ) (without duplicates) and a target number ( ), find all unique combinations in where the candidate numbers sums to . The same repeated number may be chosen from unlimited number of times. Note:
Example 2: | 給定一個無重複元素的數組 和一個目标數 ,找出 中所有可以使數字和為 的組合。 中的數字可以無限制重複被選取。 說明:
示例 2: |
思路:看到這種求所有解的情況,類似于排列組合,可以用dfs或者bfs。此題用dfs寫一個遞歸程式就可以求所有 可能情況了。
class Solution {
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> res;
dfs(candidates,target,0,{},res);
return res;
}
void dfs(vector<int>& candidates, int target,int start,vector<int> out,
vector<vector<int>> &res)
{
if(target<0) return;
else if(target==0)
{
res.push_back(out);
return;
}
for(int i=start;i<candidates.size();++i)
{
out.push_back(candidates[i]);
dfs(candidates,target-candidates[i],i,out,res);
out.pop_back();
}
}
};
class Solution:
def combinationSum(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
def dfs(candidates,target,start,path,res):
if target==0:
return res.append(path+[])
for i in range(start,len(candidates)):
if target-candidates[i]>=0:
path.append(candidates[i])
dfs(candidates,target-candidates[i],i,path,res)
path.pop()
res=[]
dfs(candidates,target,0,[],res)
return res