Backtracking Min options to sum a number using 1, 5 and 7 via recursion - JAVA

Question

I want to create a recursion function that returns the minimum options to create a certain number using numbers 1, 5 and 7 (Fixed predetermined numbers). It is important that this is done only by recursion without loops at all.

For example:

if n = 10 then it is given to the scheme by 5 + 5 which is 2 numbers, so this is the minimum and this is what we will get (as opposed to 7 + 1 + 1 + 1 or 5 + 1 + 1 + 1 + 1 + 1 that is 4 or 6 Options that are longer).

If n = 6 then we get a result of 2 (because it is given as a sum of 1 + 5).

If n = 5 (or 7 or 1) then we get a result of 1 (because it is given by the number only).

class TEST { 

static int countMin( int S[], int m, int n ,int min) 
    { 
        if (n == 0) 
            return 1;      
        if (n < 0) 
            return 0; 
        if (m <=0 && n >= 1) 
            return 0; 
        return Math.min(min,countMin( S, m - 1, n ,min-1) + countMin( S, m, n-S[m-1],min-1 )); 
    } 

public  static int f(int n)  {
      int arr[] = {1, 5, 7};  
      return countMin(arr, arr.length, n,n);
} 

    public static void main(String[] args) 
    { 
        int n = 10;
        System.out.println("The number "+n+ " - " + f(n) + " minimum options to create");
        int n2 = 7;
        System.out.println("The number "+n2+ " - " + f(n2) + " minimum options to create"); 
        int n3 = 6;
        System.out.println("The number "+n3+ " - " + f(n3) + " minimum options to create");

    } 

} 

I get for n = 10 and n = 5 for the correct result but not for n = 6 which should return 2.

*I've used this link: https://www.geeksforgeeks.org/coin-change-dp-7/

Answer 1

Think of a tree where each node has a value and has 3 children with its value decremented respectively by 7, 5, and 1

So node with total 15 would have children with values 8, 10, 14

We can start with first node having your total, and calculate each level and stop when we find a child worth 0. We also stop looking at a child if its value is less than 0.

For 10 for example:

                10
            /    |    \
        3        5       9
      / | \    / | \   / | \
    -4 -2 2   -2 0 4   2 4 1

We find zero at depth 2

private static int calculate(int total, int depth) {
    if (total == 0)
        return depth;
    else {
        int i = total - 7  >= 0 ? calculate(total - 7, depth+1) : Integer.MAX_VALUE;
        int j = total - 5  >= 0 ? calculate(total - 5, depth+1) : Integer.MAX_VALUE;
        int k = total - 1  >= 0 ? calculate(total - 1, depth+1) : Integer.MAX_VALUE;
        return Collections.min(Arrays.asList(i, j, k));
    }
}

This

int n = 10;
System.out.println("The number "+n+ " - " + calculate(n, 0) + " minimum options to create");
n = 7;
System.out.println("The number "+n+ " - " + calculate(n, 0) + " minimum options to create");
n = 6;
System.out.println("The number "+n+ " - " + calculate(n, 0) + " minimum options to create");
n = 18;
System.out.println("The number "+n+ " - " + calculate(n, 0) + " minimum options to create");

Outputs this

The number 10 - 2 minimum options to create
The number 7 - 1 minimum options to create
The number 6 - 2 minimum options to create
The number 18 - 4 minimum options to create

EDIT: The same in a funky lambda style:

private static int calculate(int total, int depth) {
    return total == 0 ? 
        depth : 
        Stream.of(7, 5, 1)
              .map(i -> total - i  >= 0 ? calculate(total - i, depth+1) : Integer.MAX_VALUE)
              .min(Integer::compare)
              .get();
}