// Arup Guha
// 11/15/05 (written)
// This is a skeleton for lab assignment #9. Your job is to fill in the
// one function that is left empty. The goal of this function is to take
// as input a subset sum instance and output a partition instance, that
// has a solution if and only if the original subset sum instance has a
// solution.

import java.io.*;
import java.util.*;

public class SubsetSumReduc {

  // This is a main that is set up to test out your reduction.
  // You should adjust the target to see if your reduction works,
  // or try different targets.

  public static void main(String[] args) throws IOException {

    int[] testarray = new int[10];
    Random rand = new Random();

    // Fill in array here and target here.
    for (int i=0; i<10; i++)
      testarray[i] = Math.abs(rand.nextInt())%1000;
    int target = Math.abs(rand.nextInt()%3000);

    // Print out array and target for debugging purposes.
    System.out.print("Array values: ");
    for (int i=0; i<10; i++)
      System.out.print(testarray[i]+" ");
    System.out.println("\ntarget = " + target);

    // Solve the Subset Sum problem by reduction.
    if (SubsetSum(testarray, target))
      System.out.println("The target value of " + target + " is achievable.");
    else
      System.out.println("The target value of " + target + " is not achievable.");
  }


  // Given a subset sum instance, this function returns a Partition instance
  // that has a solution if and only if the subset sum instance does.
  // Note that all elements in the input array AND output array must be
  // non-negative integers. The target must be a non-negative integer also.
  public static int[] fReduc(int[] values, int target) {



  }

  // Solves Partition problem, assuming that all the elements stored in
  // values are non-negative integers.
  public static boolean Partition(int[] values) {

    int sum = 0, i, j;

    // Determine the sum of values.
    for (i=0; i<values.length; i++)
      sum += values[i];

    // If it's odd there can not be a solution.
    if (sum%2 == 1) 
      return false;

    // Run the regular DP subset sum algorithm. See if there is a subset
    // that adds up to sum/2.

    // Initialize the array here. If ss[i] is false, there is no subset
    // that adds up to i yet.
    boolean[] ss = new boolean[sum/2+1];
    ss[0] = true;
    for (i=1; i<ss.length; i++)
      ss[i] = false;
  
    // Fill in the array, keeping track of new subset sums found.
    for (i=0; i<values.length; i++) 
      for (j=ss.length-1; j>=values[i]; j--)
        if (ss[j-values[i]])
          ss[j] = true;

    // Return whether or not there's a subset that adds up to sum/2.
    return ss[ss.length-1];
  }

  // Solves Subset Sum problem assuming a solution to Partition.
  // Shows a many-to-one mapping of Subset Sum to Partition.
  public static boolean SubsetSum(int[] values, int target) {

    return Partition(fReduc(values,target));
  }

}