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}