Coded Algorithm for number of ways to cross a room

Question

I am presented with a problem where I am given a room of size n, and a number of steps that I can take to get across the room. The room will always be an integer size, and so will the steps. The same step can be taken multiple times. My goal is to find the total number of possible ways to cross the room without going past the size of the room. An example of user input would be

5 9 1 3 5

Where the first integer, 5, is the size of the room, and 9 1 3 5 are the possible steps I can take. The function/algorithm would return something like this

5 //Room size

1 1 1 1 1

1 1 3

1 3 1

3 1 1

5

Conceptually, I am very aware of what is going on, I have made note that the function appears to start with the lowest values and build from there. The problem I am having is getting this from my head, into working code, any tips, pointers, or code snippets would be greatly appreciated! Thanks in advanced to any help anyone may be able to offer.

Current Code that I have been working on / with

public static void main(String[] args) {
        Scanner Scan = new Scanner(System.in);
        int ArraySize;

        int[] num = new int[100];
        int temp;
        int i, n, j;
        int roomLength;
        System.out.println("Size of Room: ");
        roomLength = Scan.nextInt();
        System.out.println("\nTotal numbers that will be entered: ");
        n = Scan.nextInt();
        System.out.println("\nNumbers:");
        for (i = 0 ; i < n; i++){
            num[i] = Scan.nextInt();
        }
        for (j = 1; j <= n; j++) {
            for (i = 0; i < n-1; i++) {
                temp = num[i];
                num[i] = num[i+1];
                num[i+1] = temp;
                uniqueCombinations(num, n, roomLength);
            }
        }
    }

    public static int uniqueCombinations(int num[], int n, int rl){
        int i;
        int value = 0;
        int placeHolder;
        for (i = 0 ; i < n ; i++){
            value += num[i];
            placeHolder = i;
            if(value == rl){
                for (i = 0 ; i <= placeHolder; i++){
                    System.out.print(num[i]);
                }
                System.out.println("");
                break;
            }
        }
        return 0;
    }

}

example run:

Size of Room: 10

Total numbers that will be entered: 5

Numbers:1 2 3 4 5

2134

2314

2341

451

451

541

514

1234

I am not sure how to account for the situations such as 1 1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 2 etc...

Answer 1

at first I thought I found a simple way to solve it using recursivity.

Quick FALSE PHP function --

<?php
function print_step($size, $steps, $key)
{
    // get the step value
    $nb = $steps[$key];

    while ($size >= $nb)
    {
        $size = $size - $nb;
        echo $nb.' ';
    }
    if ($size > 0 && $key > 0)
    {
        print_step($size, $steps, $key - 1);
    }
}

$room_size = 5;
$steps = array(4, 9, 1, 3, 5, 2);
$total_steps = count($steps);    

// order steps by lowest value (1, 2, 3, 4, 5, 9)
sort($steps);    

// 1 to size(steps)
for ($i=1; $i <= $total_steps; $i++) {
    // from 9 to 1
    print_step($room_size, $steps, ($total_steps - $i));
    echo '<br>';
}

Ouput :

5              // starting from 9
5              // starting from 5
4 1            // starting from 4
3 2            // starting from 3
2 2 1          // starting from 2
1 1 1 1 1      // starting from 1

And then you can remove duplicates, but with this solution I couldn't get every combinaison (2,1,1,1 for example).

I think you will have to find every combinaisons of every step first, and then look for the possible steps.

Example of PHP code to find equivalent values --

<?php

function find_eq($size, $steps, $key)
{
    $ret = array();
    $nb = $steps[$key];
    while ($size >= $nb)
    {
        $size = $size - $nb;
        $ret[] = $nb;
    }
    if ($size > 0 && $key > 0)
    {
        $ret = array_merge($ret, find_eq($size, $steps, $key - 1));
    }
    return $ret;
}

$steps = array(4, 9, 1, 3, 5, 2);

// order steps by lowest value (1, 3, 4, 5, 9)
sort($steps);    

$tot_eqs = array();

// From 1 to 9
foreach ($steps as $key => $value) {

    $eqs = array();

    // smallest so no equivalent
    if ($key == 0) continue;    

    //find eq from (key - 1) to 0
    for ($i = ($key - 1); $i >= 0 ; $i--) {
        $eqs[] = find_eq($value, $steps, $i);
    }
    $tot_eqs[$value] = $eqs;
}    

var_dump($tot_eqs);
//then find possibles steps and print all equivalent values for each step

Output :

array (size=5)

2 =>
    => [1, 1]

3 =>
    => [2, 1]
    => [1, 1, 1]

4 =>
    => [3, 1]
    => [2, 2]
    => [1, 1, 1, 1]

5 => 
    => [4, 1]
    => [3, 2]
    => [2, 2, 1]
    => [1, 1, 1, 1, 1]

9 =>
    => [5, 4]
    => [4, 4, 1]
    => [3, 3, 3]
    => [2, 2, 2, 2, 1]
    => [1, 1, 1, 1, 1, 1, 1, 1, 1]

Hope this could help !