001// Exercise 1.4.14 (Solution published at http://algs4.cs.princeton.edu/)
002package algs14;
003import stdlib.*;
004/* ***********************************************************************
005 *  Compilation:  javac FourSum.java
006 *  Execution:    java FourSum < input.txt
007 *
008 *  A program with N^4 running time. Read in N int integers
009 *  and counts the number of 4-tuples that sum to exactly 0.
010 *
011 *  Limitations
012 *  -----------
013 *     - we ignore integer overflow
014 *
015 *************************************************************************/
016
017public class XFourSum {
018
019        // print distinct 4-tuples (i, j, k, l) such that a[i] + a[j] + a[k] + a[l] = 0
020        public static int printAll(int[] a) {
021                int N = a.length;
022                int cnt = 0;
023                for (int i = 0; i < N; i++) {
024                        for (int j = i+1; j < N; j++) {
025                                for (int k = j+1; k < N; k++) {
026                                        for (int l = k+1; l < N; l++) {
027                                                if (a[i] + a[j] + a[k] + a[l] == 0) {
028                                                        StdOut.println(a[i] + " " + a[j] + " " + a[k] + " " + a[l]);
029                                                        cnt ++;
030                                                }
031                                        }
032                                }
033                        }
034                }
035                return cnt;
036        }
037
038        // return number of distinct 4-tuples (i, j, k, l) such that a[i] + a[j] + a[k] + a[l] = 0
039        public static int count(int[] a) {
040                int N = a.length;
041                int cnt = 0;
042                for (int i = 0; i < N; i++) {
043                        for (int j = i+1; j < N; j++) {
044                                for (int k = j+1; k < N; k++) {
045                                        for (int l = k+1; l < N; l++) {
046                                                if (a[i] + a[j] + a[k] + a[l] == 0) {
047                                                        cnt++;
048                                                }
049                                        }
050                                }
051                        }
052                }
053                return cnt;
054        }
055
056        public static void main(String[] args)  {
057                StdIn.fromFile ("data/100ints.txt");
058                int[] a = StdIn.readAllInts();
059                int cnt = count(a);
060                StdOut.println(cnt);
061                if (cnt < 10) {
062                        printAll(a);
063                }
064        }
065}