# LeetCode题目：Combination Sum，动态规划

Combination Sum
Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
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]

```class Solution {
public:
vector > combinationSum(vector &candidates, int target) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if (candidates.size() == 0)
return vector >();
sort(candidates.begin(),candidates.end());
vector > > *pR = new vector > >(target + 1);
vector > > *pT = new vector > >(target + 1);
for (int t = 1; t <= target; ++ t)
{
int c = candidates[0];
if (t % c == 0)
{
(*pR)[t].push_back(vector(t/c,c));
}
}
for (int k = 1; k < candidates.size(); ++k)
{
int ck = candidates[k];
for (int t = 1 ; t <= target; ++t)
{
(*pT)[t].clear();
for (int p = 0; p * ck <= t; ++p)
{
int remain = t - ck * p;
if (remain == 0)
{
(*pT)[t].push_back(vector(p,ck));
}
else
{
vector > &rRemain = (*pR)[remain];
for (int irr = 0; irr < rRemain.size() ;++ irr)
{
vector newSum(rRemain[irr]);
for(int ip = 0; ip < p; ++ip)
newSum.push_back(ck);
(*pT)[t].push_back(newSum);
}
}
}
}
vector > > *pTemp = pR;
pR = pT;
pT = pTemp;
}
return (*pR)[target];
}
};
```

## “LeetCode题目：Combination Sum，动态规划”上的21条回复

traveller说：

DP的要求是降低子问题的重复计算，在我的这段代码里，我将这些子问题的计算结果都存放在数组里，所以每一个子问题，实际上只需要计算一次。通过这样的方法来提高速度。

traveller说：

traveller说：

schou说：

i don’t quite understand why this is a DP problem. My Java code could pass large judge around 700ms.

public class Solution {
public ArrayList<ArrayList> combinationSum(int[] candidates, int target) {
// Start typing your Java solution below
// DO NOT write main() function
ArrayList<ArrayList> result = new ArrayList<ArrayList>();
if(candidates == null || candidates.length == 0)
return result;

Arrays.sort(candidates);
if(candidates[0] > target)
return result;

ArrayList one = new ArrayList();
find(candidates, 0, candidates.length, target, result, one);
return result;
}

private void find(int[] candidates, int start, int end, int target, ArrayList<ArrayList> result, ArrayList one) {
if(target == 0) {
return;
}

for(int i = start; i < end; i++) {
if(target < candidates[i])
continue;

target -= candidates[i];

find(candidates, i, end, target, result, one);
target += one.remove(one.size()-1);
}
}
}

traveller说：

traveller说：

Ah, your algorithm is simpler than mine.
I turned this problem in a DP problem by solving the set of sub-problem of “What combinations will add up to ‘sum’? “, while the sum from 1 to target.
The point is that, when we know “what combinations will add up to a sum from 1 to k-1”, we can easily calculate “what combinations will add up to a sum of k”, and avoid a lot of sub-problem calculation with looking up the vector than stored the previous calculation result.
However, the algorithm can be speeded up by carefully choose the step of sum increasing. Some input, we can select a much higher value than 1.

Yes, DFS will be faster than my algorithm, because of the step selection. In my code, that is 1, but for most input, a much higher value is applicable, and will speed up the calculation.

lzj说：

``` public ArrayList<ArrayList> combinationSum(int[] candidates, int target) { // Start typing your Java solution below // DO NOT write main() function Arrays.sort(candidates);```

``` ArrayList<ArrayList> result = new ArrayList<ArrayList>(); int len = candidates.length; if (len == 0 || candidates[0] > target) { return result; } ArrayList current = new ArrayList(); for (int i = 0; i < len && candidates[i] 0 && candidates[i] == candidates[i - 1]) { continue; } work(candidates, i, target, current, result); } return result; } private void work(int[] candidates, int start, int target, ArrayList current, ArrayList<ArrayList> result) { int size = current.size(); int len = candidates.length; for (int i = 1; i * candidates[start] <= target; ++i) { current.add(candidates[start]); int inc = i * candidates[start]; int removePos = current.size(); if (target - i * candidates[start] == 0) { result.add(deepCopy(current)); break; } else { int next = start + 1; while (next < len && candidates[start] == candidates[next]) { ++next; } while (next < len && candidates[next] <= target - inc) { work(candidates, next, target - inc, current, result); ++next; removeFrom(current, removePos); } } } removeFrom(current, size); } private void removeFrom(ArrayList a, int start) { int size = a.size(); for (int i = size - 1; i >= start; --i) { a.remove(i); } } ```

``` private ArrayList deepCopy(ArrayList src) { int size = src.size(); ArrayList result = new ArrayList(); for (int i = 0; i < size; ++i) { result.add(src.get(i)); } return result; } ```

lzj说：

public ArrayList<ArrayList> combinationSum(int[] candidates, int target) {
// Start typing your Java solution below
// DO NOT write main() function
Arrays.sort(candidates);

ArrayList<ArrayList> result = new ArrayList<ArrayList>();
int len = candidates.length;
if (len == 0 || candidates[0] > target) {
return result;
}
ArrayList current = new ArrayList();
for (int i = 0; i < len && candidates[i] 0 && candidates[i] == candidates[i – 1]) {
continue;
}
work(candidates, i, target, current, result);
}
return result;
}

private void work(int[] candidates, int start, int target, ArrayList current,
ArrayList<ArrayList> result) {
int size = current.size();
int len = candidates.length;
for (int i = 1; i * candidates[start] <= target; ++i) {
int inc = i * candidates[start];
int removePos = current.size();
if (target – i * candidates[start] == 0) {
break;
} else {
int next = start + 1;
while (next < len && candidates[start] == candidates[next]) {
++next;
}
while (next < len && candidates[next] <= target – inc) {
work(candidates, next, target – inc, current, result);
++next;
removeFrom(current, removePos);
}
}
}
removeFrom(current, size);
}

private void removeFrom(ArrayList a, int start) {
int size = a.size();
for (int i = size – 1; i >= start; –i) {
a.remove(i);
}
}

private ArrayList deepCopy(ArrayList src) {
int size = src.size();
ArrayList result = new ArrayList();
for (int i = 0; i < size; ++i) {
}
return result;
}

lzj说：

tag里面

[…] uniEagle Arts Skip to content 首页留言板 « LeetCode题目：Combination Sum，动态规划 LeetCode题目：Combination，C(k,n)，从n中选出k个 […]