Ndtyjky

Given an array size n, and a positive number max(max represent the range of the numbers that we can use to place in the array).

I would like to count how many combinations of sorted numbers I can place in the array.

For example :

If n = 3, max = 2.(the only numbers we can use is 1/2 as max is 2) so there are 4 combinations of sorted arrays

 1. {1,1,1}

 2. {1,1,2}

 3. {1,2,2}

 4. {2,2,2}

I wrote some code and succeed to pass this specific example but any other example that max > 2 doesn't return the correct answer.

the problem as I identify it is when the recursion reaches the last index it doesn't try a third number it just folds back.

my code :

private static int howManySorted(int n, int max, int index, int numToMax, int prevNum) {        

    // If the value is bigger then max return 0

    if(numToMax > max) {

        return 0;

    }

    if (numToMax < prevNum) {

        return 0;

    }

    //If Index reached the end of the array return 1

    if(index == n) {

        return 1;

    }



    int sortTwo =  howManySorted(n, max, index+1, numToMax, numToMax);

    int sortOne =  howManySorted(n, max, index+1, numToMax+1, numToMax);

    return ((sortOne+sortTwo));

}



public static int howManySorted(int n, int max) {

    return howManySorted(n, max, 0, 1, 0);

}

I think you would need to change your two recursive calls (this is why it only reaches value 2) and do as many calls as your max parameter:

private static int howManySorted(int n, int max, int index, int numToMax, int prevNum) {

    // If the value is bigger then max return 0

    if (numToMax > max) {

        return 0;

    }

    if (numToMax < prevNum) {

        return 0;

    }

    //If Index reached the end of the array return 1

    if (index == n) {

        return 1;

    }



    int result = 0;

    for (int i = 0; i < max; i++)

        result += howManySorted(n, max, index + 1, numToMax + i, numToMax);



    return result;

}

I believe you can simplify your answer to something like this

private static long howManySorted(int length, int min, int max) {

    if (length == 1) {

        return max - min + 1;

    }



    // if (min == max) {

    //    return 1;

    // }



    long result = 0;

    for (int i = min; i <= max; i++) {

        result += howManySorted(length - 1, i, max);

    }

    return result;

}



public static long howManySorted(int length, int max) {

    if ((length < 1) || (max < 1)) {

        throw new IllegalArgumentException();

    }



    return howManySorted(length, 1, max);

}

Client should call the public method.

So as you can see terminate conditions are when remaining length is 1, or min reaches max. Even removing the second terminate condition doesn't change the result, but can improve the performance and number of recursions.

Just test my code, I think it figures out your problem:

class Test {

private static int howManySorted(int n, int max) {

    //Better time complexity if u use dynamic programming rather than recursion.



    if (n == 0) return 1;



    int res = 0; // "res" can be a very large.



    for (int i = n; i >= 1; i--) {

        for (int j = max; j >= 1;j--) {

            res += howManySorted(i-1, j-1);

        }

    }



    return res;

}



public static void main(String args) {

    System.out.println(howManySorted(3, 2));

}

}

This code will run faster if you use dynamic programming and be careful about the answer, it could be a very large integer.