import java.io.*;
import java.util.*;

/*
Given an array consists of non-negative integers, your task is to count the number of triplets chosen
from the array that can make triangles if we take them as side lengths of a triangle.
Example 1:
Input: [2,2,3,4]
Output: 3
Explanation:
Valid combinations are:
2,3,4 (using the first 2)
2,3,4 (using the second 2)
2,2,3


[2,2,3,4]
 i   j k

set = {(2,3,4),}
i = 0
j = 2
k = 3

Note:
The length of the given array won't exceed 1000.
The integers in the given array are in the range of [0, 1000].

 */

class Solution {

  public static void main(String[] args) {
    // int[] arr = new int[]{2, 2, 3, 4};   // 1, 1, 1, 2,
    // System.out.println(String.format("Expected=%d, found=%d", 3, findCombinations(arr)));

    int[] arr = new int[]{1, 1, 1, 2};   // 1, 1, 1, 2, 3, 4
    // 1, 2,   2,   3, 4  2, - Julia explained the two pointer technique alternative design.
    //   left         right
    //
    System.out.println(String.format("Expected=%d, found=%d", 1, findCombinations(arr)));
  }

  private static Integer findCombinations(int[] arr) {

    if (arr == null || arr.length == 0) return 0;

    int num = 0;
    Arrays.sort(arr);
    for (int i = 0; i < arr.length - 2; i++) {
      int j = i + 1;
      int k = arr.length - 1;
      num += findCombinations(arr, i, j, k);
    }

    return num;
  }

  private static int findCombinations(int[] arr, int i, int j, int k) {
    if (j >= k) return 0;
    int num = 0;
    if (arr[i] + arr[j] > arr[k]) {
      System.out.println(String.format("Found combination i=%d, j=%d, k=%d", i, j, k));
          num++;  // design has defect -> not efficient -> n^2 increment -> add range of number/
    } else {

    }

    num += findCombinations(arr, i, j + 1, k);
    num += findCombinations(arr, i, j, k - 1);
    return num;
  }
}