``` 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 ``` ```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; } } } ```