# Iterative Java DP solution

• Hi guys!

The main idea reminds an approach for solving coins/knapsack problem - to store the result for all i < target and create the solution from them. For that for each t from 1 to our target we try every candidate which is less or equal to t in ascending order. For each candidate "c" we run through all combinations for target t-c starting with the value greater or equal than c to avoid duplicates and store only ordered combinations.

``````public class Solution {
public List<List<Integer>> combinationSum(int[] cands, int t) {
Arrays.sort(cands); // sort candidates to try them in asc order
List<List<List<Integer>>> dp = new ArrayList<>();
for (int i = 1; i <= t; i++) { // run through all targets from 1 to t
List<List<Integer>> newList = new ArrayList(); // combs for curr i
// run through all candidates <= i
for (int j = 0; j < cands.length && cands[j] <= i; j++) {
// special case when curr target is equal to curr candidate
// if current candidate is less than the target use prev results
else for (List<Integer> l : dp.get(i-cands[j]-1)) {
if (cands[j] <= l.get(0)) {
List cl = new ArrayList<>();
}
}
}
}
return dp.get(t-1);
}
}
``````

Hope it helps!

• Why is it i-cands[j]-1, not i-cands[j]?

• Hi, that's because we start filling list dp from zero index, not from 1, but targets we are interested in are within [1,t].

• It seems a typical dp question. But why are the top answers using backtracking?...

• confusing why need to check " if (cands[j] <= l.get(0)) " ?

• @annieqt, I have the same question in my mind right now when I looked at this question 3 months afters solving it using back tracking.

• thanks for this nice answer. I just wonder, would there be any relative performance disadvantage comparing to dfs when in cases where both the target and the candidates are large, e.g. target=1000000, candidates=[499999,500001]?

• I agree with you. Anyway this is a nice coding

• @coolth To keep cl in asc order.

• @coolth check " if (cands[j] <= l.get(0)) " to remove dulplicate.

• @annieqt I think it's more straightly to use backtracking than dp.

• what is the time complexity of this solution? Is it O(t^2 * size_of_array) ?

• I found this solution was slower than the backtracking in my local environment.

• @stonepeter Could you please explain more how can `if (cands[j] <= l.get(0))` remove duplicate?
Or could anyone explain it?
Thanks!

• I run the codes in eclipse and there's error when iterate the dp "for (List<Integer> l : dp.get(i-cands[j]-1))"

• @sculd because dp[i] i is begin 0.

• Thanks for sharing this solution, here is my Python version based on the same idea

``````class Solution(object):
def combinationSum(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
candidates.sort()
dp = []
# run through all target from 1 to target
for i in xrange(1, target + 1):
# run through all candidates which is smaller than i
new_dp = []
for j in xrange(len(candidates)):
# skip candidate which is larger than current target
if candidates[j] > i:
break
# special case
if candidates[j] == i:
new_dp.append([candidates[j]])
else:
if i - candidates[j] - 1 >= 0:
new_dp.extend(comb + [candidates[j]] for comb in dp[i - candidates[j] - 1] if candidates[j] >= comb[-1])
dp.append(new_dp)

return dp[-1]
``````

• It seems that's better solution than backtracking on time complex (O(n*target) vs O(n!)) but if you use this solution to submit it slow than the most

• Here's the same idea, but you fill the `dp` array starting with 0 which means the solution is in `dp[target]` instead of `dp[target-1]`

``````class Solution:
def combinationSum(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
candidates = set(candidates)
solns = {0: [()]}
for i in range(1, target+1):
solns[i] = []
for j in range(0, i+1):  # note: this can be rewritten as for i-j in candidates with a little work...
if i-j == 0 or i-j in candidates:
solns[i].extend(
soln + (i-j,)
for soln in solns[j]
if not (soln and i-j < soln[-1])
)
return solns[target]
``````

• @sheng_sang Why is it slower in fact? It confuses me

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.