Dynamic Programming Altogorithm

Question

I'm trying to construct an algorithm that runs at O(nb) time with the following input/question: input: an array A[1..n] of n different integers and an integer b (i am assuming that the numbers in A are sequential, starting at 1 ending at n, i.e. for n=4 A[1,2,3,4]. question: in how many ways can b be written as the sum of elements of the array when elements in A[] can only be used once?

I've kind of hit a wall on this one. I'm looking for some kind of recursive solution, but I don't see how to avoid using repeat numbers. Like, for instance, if we started at 1 and stored all the ways to make one (just 1) then 2 (just 2) then three (3 or 2+1) etc, it shouldn't be hard to see how many ways we can make larger numbers. But if, for instance, we take 5, we will see that it can be broken into 4+1, and 4 can be further broken down into 3+1, so then we would see 2 solutions (4+1, and 3+1+1), but one of those has a repeat of a number. Am I missing something obvious? Thanks so much!

Answer 1

Let F(x,i) be the number of ways elements of A[1:i] can be summed to get x.

F(x,i+1) = F(x-A[i+1],i) + F(x,i)

That is it!

Answer 2

Recursive and dynamic solutions in C:

#include <stddef.h>
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

typedef unsigned char uchar;
typedef unsigned int uint;

typedef struct tAddend
{
  struct tAddend* pPrev;
  uint Value;
} tAddend;

void findRecursiveSolution(uint n, uint maxAddend, tAddend* pPrevAddend)
{
  uint i;

  for (i = maxAddend; ; i--)
  {
    if (n == 0)
    {
      while (pPrevAddend != NULL)
      {
        printf("+%u", pPrevAddend->Value);
        pPrevAddend = pPrevAddend->pPrev;
      }
      printf("\n");
      return;
    }

    if (n >= i && i > 0)
    {
      tAddend a;
      a.pPrev = pPrevAddend;
      a.Value = i;
      findRecursiveSolution(n - i, i - 1, &a);
    }

    if (i <= 1)
    {
      break;
    }
  }
}

void printDynamicSolution(uchar** pTable, uint n, uint idx, uint sum, tAddend* pPrevAddend)
{
  uchar el = pTable[idx][sum];

  assert((el != 0) && (el != 5) && (el != 7));

  if (el & 2) // 2,3,6 - other(s)
  {
    printDynamicSolution(pTable,
                         n,
                         idx - 1,
                         sum,
                         pPrevAddend);
  }

  if (el & 4) // self + other(s)
  {
    tAddend a;
    a.pPrev = pPrevAddend;
    a.Value = idx + 1;

    printDynamicSolution(pTable,
                         n,
                         idx - 1,
                         sum - (idx + 1),
                         &a);
  }

  if (el & 1) // self, found a solution
  {
    tAddend a;
    a.pPrev = pPrevAddend;
    a.Value = idx + 1;

    pPrevAddend = &a;
    while (pPrevAddend != NULL)
    {
      printf("+%u", pPrevAddend->Value);
      pPrevAddend = pPrevAddend->pPrev;
    }
    printf("\n");
  }
}

void findDynamicSolution(uint n)
{
  uchar** table;
  uint i, j;

  if (n == 0)
  {
    return;
  }

  // Allocate the DP table

  table = malloc(sizeof(uchar*) * n);

  if (table == NULL)
  {
    printf("not enough memory\n");
    return;
  }

  for (i = 0; i < n; i++)
  {
    table[i] = malloc(n + 1);

    if (table[i] == NULL)
    {
      while (i > 0)
      {
        free(table[--i]);
      }

      free(table);
      printf("not enough memory\n");
      return;
    }
  }

  // Fill in the DP table

  for (i = 0; i < n; i++)
  {
    for (j = 0; j <= n; j++)
    {
      if (i == 0)
      {
        table[i][j] = (i + 1 == j); // self
      }
      else
      {
        table[i][j] = (i + 1 == j) + // self
          2 * (table[i - 1][j] != 0) + // other(s)
          4 * ((j >= i + 1) && (table[i - 1][j - (i + 1)] != 0)); // self + other(s)
      }
    }
  }

  printDynamicSolution(table, n, n - 1, n, NULL);

  for (i = 0; i < n; i++)
  {
    free(table[i]);
  }

  free(table);
}

int main(int argc, char** argv)
{
  uint n;

  if (argc != 2 || sscanf(argv[1], "%u", &n) != 1)
  {
    n = 10;
  }

  printf("Recursive Solution:\n");
  findRecursiveSolution(n, n, NULL);

  printf("\nDynamic Solution:\n");
  findDynamicSolution(n);

  return 0;
}

Output: for 10:

Recursive Solution:
+10
+1+9
+2+8
+3+7
+1+2+7
+4+6
+1+3+6
+1+4+5
+2+3+5
+1+2+3+4

Dynamic Solution:
+1+2+3+4
+2+3+5
+1+4+5
+1+3+6
+4+6
+1+2+7
+3+7
+2+8
+1+9
+10

See also on ideone.

Answer 3

This is not a dynamic programming solution though. Non-recursive. Assumption that arr is sorted in your case like [i....j] where a[i] <= a[j] That's easy enough

void summer(int[] arr, int n , int b)
{
    int lowerbound = 0;
    int upperbound = n-1;
    while (lowerbound < upperbound)
    {
         if(arr[lowerbound]+arr[upperbound] == b)
         {
              // print arr[lowerbound] and arr[upperbound]
              lowerbound++; upperbound--;
         }
         else if(arr[lowerbound]+arr[upperbound] < b)
              lowerbound++;
         else
              upperbound--;
    }

}

The above program is easily modifiable to a recursive you need to only change the function definition by passing lowerbound and upperbound.

Case for termination is still lowerbound < upperbound Base case is if arr[lowerbound] +arr[upperbound] == b

Edited based on comments

You will need to use a modified version of integer knapsack problem. The values of [i,j] both need to be modified accordingly. You are having the problem because you are not most probably modifying your i carefully, Increase your i accordingly then their will not be repetition like the one you are having.