NumberOfSolutionsSnippet.java

 public long count() {
    if(n < 0) {
      //since the variables take only non-negative values
      //there is no solution in this case
      return 0;
    }
    
    C = new long[n+r+1][n+r+1];
    fillC();
    
    long count = 0;
    long S = nCr(n+r-1, r-1);
    for(int subsetSize=1; subsetSize < r; subsetSize++) {
      count += Math.pow(-1, subsetSize-1) * countOverSubsets(subsetSize);
    }
    return S-count >= 0 ? S-count : 0;
  }
  
  /**
   * Subsets of size subsetSize from r.
   * This is the same as standard print all combinations code
   * where we are trying to pick a subset of size subsetSize
   */
  private long countOverSubsets(int subsetSize) {
    int[] col = new int[subsetSize];
    return countOverSubsets(col, r, 0, 0);
  }
  
  /**
   * pCq
   */
  private long countOverSubsets(int[] col, int p, int k, int start) {
    int q = col.length;
    
    if(k == q) {
      int sum = 0;
      for(int i = 0; i < col.length; i++) {
        //TODO: handle this more gracefully
        sum += (dMax[col[i]] - dMin[col[i]] + 1);
        
        if(sum < 0) {
          //overflow occurred.
          sum = Integer.MAX_VALUE;
        }
      }
      return nCr(n-sum+r-1, r-1);
    }
    
    long result = 0;
    for(int i = start; i < p; i++) {
      col[k] = i;
      result += countOverSubsets(col, p, k+1, i+1);
    }
    return result;
  }