All possible Combinations using Dynamic Programming

Question

I have an easy looking mathematical problem. Here is an array.

Array = { 1, 2, 3 }

Need all possible combinations from the above mentioned array elements which will make the total sum = 5.

Solution: { 1, 1, 1, 1, 1 } { 1, 1, 1, 2 } { 1, 2, 2 } { 2, 3 } { 1, 1, 3 }

Note: You may use any array element any number of times provided the sum should be 5.

        int weight = 5;
        List<int> weights = new List<int>() { 1, 2 ,3};


   void function1(int weight,List<int> weights, List<List<int>> combinationlist)
    { 
    for (int i = 0; i < weights.Count; i++)
        {
            if (weight % weights[i] == 0)
            {
                int num = weight / weights[i];
                List<int> mylist = new List<int>();
                for (int j = 0; j < num; j++)
                {
                    mylist.Add(weights[i]);

                }

                if (!combinationlist.Contains(mylist))
                    combinationlist.Add(mylist);
            }


        }


    }

Now the above function generated the easy combination of {1,1,1,1,1} Solution.

    void function2(int weight, List<int> weights, List<List<int>> combinationlist)
    {
        int i = weights.Count - 1;
        Stack<int> mystack = new Stack<int>();
        List<int> combinationarray = new List<int>();


        foreach (var x in weights)
            mystack.Push(x);

        for (;i >= 0; i--)
        {
            if (weight <= weights[i])
                mystack.Pop();  
        }


        int remainder = 0;


        if (weight % mystack.Peek() != 0)
            remainder = weight % mystack.Peek();

            int quotient = weight / mystack.Peek();

            combine(combinationlist,combinationarray,mystack,quotient,remainder);


    }

Combine function

void combine(List<List<int>>combinations,List<int>combination,Stack<int> mystack,int quotient, int remweight)
    {

        for (int i = 0; i < quotient; i++)
        {

            combination.Add(mystack.Peek());
        }

        if (remweight > 1)
            remweight = remweight - mystack.Peek() * quotient;
        else if (remweight == 0)
        {
            if (!combinations.Contains(combination))
                combinations.Add(combination);

            return;

        }

        else
            return;

        while (mystack.Peek() > remweight )
        {
            if (mystack.Count != 0)
                mystack.Pop();
        }

        quotient = remweight / mystack.Peek();


combine(combinations, combination, mystack, quotient, remweight);


        }

With all that work . I could only get two solutions {2,1,1,1} {1,1,1,1,1}.

Answer 1

Following method simplifies and gets all solutions (code is in Racket programming language). Comments explain the procedure being done:

(define L '(0 1 2 3))       ; ADD 0 TO THE LIST; 

(define outl
  (for*/list (   ; TRY ALL COMBINATIONS CHOOSING 5 NUMBERS FROM ABOVE LIST;
                 ; SINCE THAT IS MAXIMUM NUMBER OF ELEMENTS THAT CAN ADD UP TO 5;
                 ; REPETITION IS ALLOWED;
              (i L)
              (j L)
              (k L)
              (m L)
              (n L)
              #:when (= 5 (+ i j k m n)))   ; USE COMBINATION ONLY IF SUM IS 5;
  (remove* (list 0)                         ; REMOVE 0s FROM THIS COMBINATION;
           (sort (list i j k m n) <))))     ; SORT COMBINATION;

(remove-duplicates outl)                    ; REMOVE DUPLICATES FROM LIST; 

Output is a list of answer lists:

'((2 3) (1 1 3) (1 2 2) (1 1 1 2) (1 1 1 1 1))

Another solution is using recursion to keep adding all elements till sum is reached (or exceeded):

(define L '(1 2 3))
(define desired_sum 5)

(define anslist '())       ; solutions will be added to this list;

(let loop ((ol '()))       ; start with an empty list;
  (for ((i L))             ; try adding each element and see if desired sum is reached; 
    (cond
      [(= desired_sum (apply + (cons i ol)))  ; desired sum reached
       (set! anslist                          ; add sorted solution to anslist;
             (cons (sort (cons i ol) <)       ; sorting needed to identify duplicates later;
                   anslist))]        
      [(> desired_sum (apply + (cons i ol)))  ; total is less than desired sum
       (loop (cons i ol))]                    ; so loop again to add more elements;
      )))                    ; discard (no looping) if desired sum is exceeded;

(remove-duplicates anslist)  ; print after removing duplicate solutions;

Output:

'((2 3) (1 1 3) (1 2 2) (1 1 1 2) (1 1 1 1 1))

Answer 2

I'll provide an answer in python since it illustrates the algorithm well. Python is nearly like pseudo-code for such problems.

# curr: a temporary list that is used only for printing the result
# arr: the list of input values
# val: the number we want to sum to
# currval: the number used so far (that will be the maximum number used so far)
def recursive_combos(curr, arr, val, currval):
    for item in arr:
        if item < currval:
            continue
        if val - item < 0:
            return
        if val - item == 0:
            print curr + [item]
            continue
        recursive_combos(curr + [item], arr, val - item, item)
    return

def combos(arr, val):
    recursive_combos([], sorted(arr), 5, min(arr) - 1)

combos([3, 1, 2], 5)

Answer:

[1, 1, 1, 1, 1]
[1, 1, 1, 2]
[1, 1, 3]
[1, 2, 2]
[2, 3]

This is a basic illustration of recursion and I think the code is mostly self-explanatory.

The key things to note in this solution are:

1. The array needs to be sorted to help eliminate duplicates
2. The 4th parameter needs to be present to eliminate duplicates. I think you'll find it a useful exercise to eliminate it and try the code. There is likely a cleaner way to do it rather than pass the 4th parameter and you could try that out.
3. This does not use memoization that is another key-component of dynamic programming. That will need to store the results somewhere for a value and look up the answer. It can easily be plugged in though.