题目:
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