package algs14;
import java.util.Arrays;
import stdlib.*;
/* ***********************************************************************
 *  Compilation:  javac Exponential.java
 *  Execution:    java Exponential N
 *
 *  A program with exponential running time. Read in N integers
 *  and find the subset whose sum is closest to 0.
 *
 *  Limitations
 *  -----------
 *     - we assume no sum of N integers will overflow a int
 *
 *************************************************************************/

public class XExponential {

  public static double timeTrial(int N, int[] a) {
    Stopwatch s = new Stopwatch();

    // find subset closest to 0
    long best = Long.MAX_VALUE;
    int stop = 1 << N;
    for (int n = 1; n < stop; n++)  {
      long sum = 0;
      for (int i = 0; i < N; i++) {
        if (((n >> i) & 1) == 1) sum = sum + a[i];
      }
      if (Math.abs(sum) < Math.abs(best)) best = sum;
    }
    //System.out.println(best);
    return s.elapsedTime();
  }


  public static void main(String[] args) {
    int MAX = 28;
    int[] a = new int[MAX];
    for (int i = 0; i < MAX; i++)
      a[i] = StdRandom.uniform (Integer.MIN_VALUE, Integer.MAX_VALUE);
    StdOut.println(Arrays.toString (a));

    StdOut.format("%7s %7s %4s\n", "size", "time", "ratio");
    double prev = timeTrial(10, a);
    for (int N = 1; N < MAX; N += 1) {
      double curr = timeTrial(N, a);
      StdOut.format("%7d %7.2f %4.2f\n", N, curr, curr / prev);
      prev = curr;
    }
  }
}