In this example, for this type of problem, we will be creating a two-dimensional array, where one dimension, (y), represents the values of the elements (that is, costs of each expense: 5, 3, 2, 2, and 5) and the other dimension, (x), represents the total cost incrementally (that is, 0 through 10). This is why we normalize our data in the first step—it helps us in terms of keeping our array small in terms of its dimensions. 

Once we have the array, we will assign each of the array positions—arr[i][j]—as true if any of the 0 to i costs can create the j sum at any point, else it will be false:

CREATE empty 2d array with based on input data

IF expected total 0, any element can achieve this, so set [i][0] to true

IF cost of first row is less than total, set [0][cost] to true

LOOP over each row from the second row

    LOOP over each column

        IF current row cost is less than the current column total

            COPY from the row above, the value of the current column if
            it is true
                or else offset the column by current rows cost

        ELSE

            Copy value from the row above for the same column


IF last element of the array is empty

   No results found


generate_possible_outcomes()

FUNCTION generate_possible_outcomes

    IF reached the end and sum is non 0
        
       ADD cost as an option and return options

    IF reached the end and sum is 0

        return option

    IF sum can be derived without current row cost

        generate_possible_outcomes() from the previous row

    IF sum cannot be derived without current row

        ADD current row as an option
        
        generate_possible_outcomes() from the previous row

Note in the preceding code that the algorithm is quite straightforward; we just break down the problem into smaller sub-problems and try to answer the question for each sub-problem while working its way up to the bigger problem. Once we are done constructing the array, we start from the last cell of the array and then traverse up and add a cell to the path taken, based on whether the current cell is true or not. The recursive process is stopped once we reach the total of 0, that is, the first column.