The same repeated number may be chosen from C unlimited number of times.
Note:
All numbers (including target) will be positive integers.
Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
The solution set must not contain duplicate combinations.
For example, given candidate set 2,3,6,7 and target 7,
A solution set is:
[7]
[2, 2, 3]
java code : 这种递归会超时，分析原因可能是因为频繁压栈出栈，因为每一次递归有两个递归分支，换成循环迭代版本的就不会超时了：
以下代码超时：
public class Solution {
ArrayList> res;
ArrayList newcandidates;
ArrayList sum;
public ArrayList> combinationSum(int[] candidates, int target) {
// IMPORTANT: Please reset any member data you declared, as
// the same Solution instance will be reused for each test case.
res = new ArrayList>();
if(candidates.length == 0)
return res;
newcandidates = new ArrayList();
Arrays.sort(candidates);
for(int i = 0; i < candidates.length; i++)
{
int num = target / candidates[i];
for(int k = 0; k < num; k++)
newcandidates.add(candidates[i]);
}
//System.out.println(newcandidates);
if(newcandidates.size() == 0)
return res;
sum = new ArrayList();
dfs(target, 0, 0);
sum = null;
newcandidates = null;
return res;
}
public void dfs(int target, int step, int tmpsum)
{
if(step == newcandidates.size())
{
if(tmpsum == target)
{
if(!res.contains(sum))
res.add(new ArrayList
(sum));
}
return ;
}
if(tmpsum > target)
return;
sum.add(newcandidates.get(step));
dfs(target, step + 1, tmpsum + newcandidates.get(step));
sum.remove(sum.size() - 1);
dfs(target, step + 1, tmpsum);
return;
}
}
以下代码不超时：
public class Solution {
public ArrayList> combinationSum(int[] candidates, int target) {
// IMPORTANT: Please reset any member data you declared, as
// the same Solution instance will be reused for each test case.
ArrayList> res = new ArrayList>();
if(candidates.length == 0)
return res;
Arrays.sort(candidates);
ArrayList sum = new ArrayList();
dfs(res, candidates, target, sum, 0, 0);
return res;
}
public void dfs(ArrayList> res, int[] array, int target, ArrayList sum, int step, int tmpsum)
{
if(tmpsum == target)
{
if(!res.contains(sum))
res.add(new ArrayList(sum));
return;
}
if(tmpsum > target)
return;
for(int i = step; i < array.length; i++)
{
sum.add(array[i]);
dfs(res, array, target, sum, i, tmpsum + array[i]);
sum.remove(sum.size() - 1);
}
return;
}
}
如果循环里面的 dfs 函数 里，循环步长 i 变成 i +1 ，那么就变形为每个数只能用一次。