We can use a dynamic programming bottom-up approach.
public class Euler76 { public int intPartition(int n){ /* * N[i][j] is the number of ways to partition i using * integers from 1 to j inclusive. * * N[i][j] = N[i-1][j] + N[i-j][j] * (j not used) (j used) */ int N[][] = new int [n+1][n+1]; for(int i = 0; i <= n; i++){ N[0][i] = 1; } for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ if(j > i) N[i][j] = N[i][j-1]; else N[i][j] = N[i][j-1] + N[i-j][j]; } } return N[n][n-1]; } public static void main(String[] args) { System.out.println(new Euler76().intPartition(100)); } }