SubSet sum with N array Solution, Dynamic Solution recquired

Question

Though you can have any number of arrays but let's Suppose you have two arrays {1,2,3,4,5,6} and {1,2,3,4,5,6} You have to find whether they sum upto 4 with participation of both array elements. i.e.

1 from array1, 3 from array2
2 from array1, 2 from array2
3 from array1, 1 from array2

etc

In Nutshell:Want to implement SubSet Sum Algorithm where there is two arrays and array elements are chosen from both of the arrays to make up the target Sum

here is the subset sum algorithm that I use for one array

bool subset_sum(int a[],int n, int sum)
{
 bool dp[n+1][sum+1];


   int i,j;

   for(i=0;i<=n;i++)   
      dp[i][0]=true;

   for(j=1;j<=sum;j++)
        dp[0][j]=false;

   for(i=1;i<=n;i++)

    {

        for(j=1;j<=sum;j++)

       {

           if(dp[i-1][j]==true)

              dp[i][j]=true;

           else
           {

               if(a[i-1]>j)

                   dp[i][j]=false;

                else

                    dp[i][j]=dp[i-1][j-a[i-1]];

            }

        }

    }
  return dp[n][sum];
}

Answer 1

We can implement this with a 3 dimensional dp. But for simplicity and readability I have written it using two methods.

NOTE : My solution works when we choose at least one element from each array. It doesn't work if there is a condition that we have to choose equal number of elements from each array.

// This is a helper method

//  prevPosAr[] is the denotes what values could be made with participation from ALL
// arrays BEFORE the current array

// This method returns an array which denotes what values could be made with the
// with participation from ALL arrays UP TO current array


boolean[] getPossibleAr( boolean prevPossibleAr[], int ar[] )
{
    boolean dp[][] = new boolean[ ar.length + 1 ][ prevPossibleAr.length  ];
    // dp[i][j] denotes   if we can make value j using AT LEAST
    // ONE element from current ar[0...i-1]

    for (int i = 1; i <= ar.length; i++)
    {
        for (int j = 0; j < dp[i].length; j++)
        {
            if ( dp[i-1][j] == true )
            {
                // we can make value j using AT LEAST one element from ar[0...i-2]
                // it implies that we can also make value j using AT LEAST
                // one element from ar[0...i-1]
                dp[i][j] = true;
                continue;
            }

            int prev = i-ar[i-1];
            // now we look behind


            if ( prev < 0 )
            {
                // it implies that ar[i-1] > i
                continue;
            }

            if ( prevPossibleAr[prev] || dp[i-1][prev] )
            {
                // It is the main catch
                // Be careful


                // if ( prevPossibleAr[prev] == true )
                // it means that we could make the value prev
                // using the previous arrays (without using any element
                // of the current array)
                // so now we can add ar[i-1] with prev and eventually make i



                // if ( dp[i-1][prev] == true )
                // it means that we could make prev using one or more
                // elements from the current array....
                // now we can add ar[i-1] with this and eventually make i

                dp[i][j] = true;
            }
        }
    }

    // What is dp[ar.length] ?
    // It is an array of booleans
    // It denotes whether we can make value j using ALL the arrays 
    // (using means taking AT LEAST ONE ELEMENT)
    // before the current array and using at least ONE element 
    // from the current array ar[0...ar.lengh-1] (That is the full current array)

    return dp[ar.length];
}



// This is the method which will give us the output
boolean subsetSum(int  ar[][], int sum )
{
    boolean prevPossible[] = new boolean[sum+1];
    prevPossible[0] = true;


    for ( int i = 0; i < ar.length; i++ )
    {
        boolean newPossible[] = getPossibleAr(prevPossible, ar[i]); 
        // calling that helper function
        // newPossible denotes what values can be made with
        // participation from ALL arrays UP TO i th array
        // (0 based index here)



        prevPossible = newPossible;
    }

    return prevPossible[sum];
}

Answer 2

Steps,

find (Array1, Array2, N)
  sort Array1
  sort Array2

  for (i -> 0 && i < Array1.length) and (j -> Array2.length-1 && j >= 0)
    if(Array1[i] + Array2[j] == N)
      return yes;
    if(Array1[i] + Array2[j] > N)
      j--;
    else
      i++;
  return NO;