NumberOfSolutions.java

public class NumberOfSolutions {
  
  private int n;
  private int r;
  private int[] dMin;
  private int[] dMax;
  
  private long[][] C;//C[n][r] = n choose r
  
  public NumberOfSolutions(int n, int r, int[] dMin, int[] dMax) {
    assert(dMin.length == r);
    assert(dMax.length == r);
    
    this.n = n;
    this.r = r;
    this.dMin = dMin;
    this.dMax = dMax;    
    
    //We don't need the original n value anywhere
    int sigmaDMin = 0;
    for(int min: dMin) {
      sigmaDMin += min;
    }
    this.n = this.n - sigmaDMin;
  }
  
  private void fillC(){
    C[0][0] = 1;
    for(int i = 1; i <= n+r; i++){
      C[i][0] = 1;
      for(int j = 1; j <= n+r; j++){
        C[i][j] = C[i-1][j-1] + C[i-1][j];
      }
    }
  }
  
  private long nCr(int n, int r) {
    if(n < 0 || n < r) {
      return 0;
    }
    return C[n][r];
  }

  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;
  }
  
  public static void main(String[] args) {
    int[] dMin = {1,0,4,2};
    int[] dMax = {6,7,8,6};
    int n = 20;
    int r = 4;
    NumberOfSolutions nos = new NumberOfSolutions(n,r,dMin, dMax);
    System.out.println(nos.count());
  }
}