Combination of given number that add up to the target number using DP?

Question

I don't know if I describe the problem correctly. The problem is: there's the given number: 2, 3, 7, and let's say the target number is 10. Use these given numbers only, find the combination that add up to 10. For example: 2 + 2 + 2 + 2 + 2 = 10 or 3 + 7 = 10 or 7 + 3 = 10, etc.

Given that, I came up with the recursive solution (Using Javascript):

function combination(n) {
  if(n < 2) {
    return 0
  }

  if(n === 2) {
    return 1
  }

  if(n === 3) {
    return 1
  }

  if(n === 7) {
    return 4
  }

  return combination(n - 2) + combination(n - 3) + combination(n - 7)
}

However, the time of this solution is exponentially growing. So I was trying to solve this by using DP (Dynamic Programming).But I can't think a way of it.

Any ideas ? I would be grateful if someone enlighten me.

Possible duplicate of [Finding all possible combinations of numbers to reach a given sum](https://stackoverflow.com/questions/4632322/finding-all-possible-combinations-of-numbers-to-reach-a-given-sum) — thebenman, Sep 25 '17 at 08:27

score 0 · Answer 1 · answered Sep 25 '17 at 08:27

0

You could use a recursive approach by checking the sum and the index. If the values are valid, then proceed.

function combine(array, sum) {
    function iter(i, temp) {
        var total = temp.reduce((a, b) => a + b, 0);
        if (total === sum) {
            result.push(temp);
        }
        if (total >= sum || i >= array.length) {
            return;
        }
        iter(i, temp.concat(array[i]));
        iter(i + 1, temp);
    }

    var result = [];
    
    iter(0, []);
    return result;
}

console.log(combine([2, 3, 7], 10));

.as-console-wrapper { max-height: 100% !important; top: 0; }

answered Sep 25 '17 at 08:27

Nina Scholz

376,160
25
347
392

Thanks, but the answer is not complete – Mactavish Sep 25 '17 at 10:10
@Mactavish, what is missing? – Nina Scholz Sep 25 '17 at 10:18
there are some case that was not covered – Mactavish Sep 25 '17 at 11:32
@Mactavish, which ones? – Nina Scholz Sep 25 '17 at 11:34
for example, if I call combine([2, 3, 7], 7), I get two answers which was 223 and 7, but it should also include 232 and 322 – Mactavish Sep 25 '17 at 11:40
you can take the result and use a permutation algorithm to get the different order of items. – Nina Scholz Sep 25 '17 at 11:42
Anyway, I've already find a solution. Thanks for your anwser. :) – Mactavish Sep 25 '17 at 11:45

score 0 · Answer 2 · answered Sep 25 '17 at 10:08

Thank you guys, I've already figure this out by using iteration, bottom-up.

function combination(n) {
  var table = {
    '2': 1,
    '3': 1,
    '7': 4
  }
    if(n < 2) return 0
  if(table[n]) return table[n]

  for(let i = 4; i <= n; i++) {
    table[i] = (table[i - 2] ? table[i - 2] : 0) + (table[i - 3] ? table[i - 3] : 0) + (table[i - 7] ? table[i - 7] : 0)
  }
  return table[n]
}

Combination of given number that add up to the target number using DP?

2 Answers2