Iterative Java DP solution


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


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


  • 3
    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]
    

  • 0
    S

    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


Log in to reply
 

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