Iterative Java DP solution


  • 48
    S

    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 (i == cands[j]) newList.add(Arrays.asList(cands[j]));
                    // 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<>();
                            cl.add(cands[j]); cl.addAll(l);
                            newList.add(cl);
                        }
                    }
                }
                dp.add(newList);
            }
            return dp.get(t-1);
        }
    }
    

    Hope it helps!


  • 0
    S

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


  • 1
    S

    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].


  • 0

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


  • 2
    C

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


  • 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.


  • 0
    S

    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]?


  • 0
    O

    I agree with you. Anyway this is a nice coding


  • 1
    W

    @coolth To keep cl in asc order.


  • 2
    S

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


  • 0
    M

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


  • 0
    A

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


  • 0

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


  • 0
    J

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


  • 0
    R

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


  • 0
    J

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


  • 0
    N

    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]
    

Log in to reply
 

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