distributing a number among an array in java

Question

Given a number N and an array ? How to distribute N among the array as the following example:

N = 5 and array of size 4;

[5,0,0,0]
[0,5,0,0]
[0,0,5,0]
[0,0,0,5]
[4,1,0,0]
[4,0,1,0]
[4,0,0,1]
[1,4,0,0]
[0,4,1,0]
[0,4,0,1]
[1,0,4,0]
[0,1,4,0]
[0,0,4,1]
.
..
..
[2,1,2,0]
..
..
...

and so on

The important thing is that the sum of whole array is N!

I want to implement a hill climbing algorithm so I want to generate all successors, then hill climbing can choose from the list.

Answer 1

Use recursion or don't if you hate it or have long arrays. You want to fill in arr. You have filled beginning (0..index-1) and you want to fill the end of array with the rest N.

Call (arr has length 5): fill(arr, 5, 0);

private static void fill(int[] arr, int N, int index) {
    if (arr == null) {
        return;
    }
    if (N == 0) {
        for (; index < arr.length; index++) {
            arr[index] = 0;
        }
    } else if (index == arr.length - 1) {
        arr[index] = N;
    } else {
        for (int j = N; j >= 0; j--) {
            arr[index] = j;
            fill(arr, N - j, index + 1);
        }
    }

    if (index >= arr.length - 1) {
        // use your array
        System.out.println(Arrays.toString(arr));
    }
}