// Exercise 1.4.14 (Solution published at http://algs4.cs.princeton.edu/)
package algs14;
import stdlib.*;
/* ***********************************************************************
 *  Compilation:  javac FourSum.java
 *  Execution:    java FourSum < input.txt
 *
 *  A program with N^4 running time. Read in N int integers
 *  and counts the number of 4-tuples that sum to exactly 0.
 *
 *  Limitations
 *  -----------
 *     - we ignore integer overflow
 *
 *************************************************************************/

public class XFourSum {

  // print distinct 4-tuples (i, j, k, l) such that a[i] + a[j] + a[k] + a[l] = 0
  public static int printAll(int[] a) {
    int N = a.length;
    int cnt = 0;
    for (int i = 0; i < N; i++) {
      for (int j = i+1; j < N; j++) {
        for (int k = j+1; k < N; k++) {
          for (int l = k+1; l < N; l++) {
            if (a[i] + a[j] + a[k] + a[l] == 0) {
              StdOut.println(a[i] + " " + a[j] + " " + a[k] + " " + a[l]);
              cnt ++;
            }
          }
        }
      }
    }
    return cnt;
  }

  // return number of distinct 4-tuples (i, j, k, l) such that a[i] + a[j] + a[k] + a[l] = 0
  public static int count(int[] a) {
    int N = a.length;
    int cnt = 0;
    for (int i = 0; i < N; i++) {
      for (int j = i+1; j < N; j++) {
        for (int k = j+1; k < N; k++) {
          for (int l = k+1; l < N; l++) {
            if (a[i] + a[j] + a[k] + a[l] == 0) {
              cnt++;
            }
          }
        }
      }
    }
    return cnt;
  }

  public static void main(String[] args)  {
    StdIn.fromFile ("data/100ints.txt");
    int[] a = StdIn.readAllInts();
    int cnt = count(a);
    StdOut.println(cnt);
    if (cnt < 10) {
      printAll(a);
    }
  }
}