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/

Seems like you are looking into coin change problem or something of the kind. I think this answer (https://stackoverflow.com/questions/40804598/minimum-number-of-coins-for-a-given-sum-and-denominations) might be helpful. — Igor Nikolaev, Feb 05 '19 at 21:06
I think this is a standard programming question, I would suggest to see the problems like (https://www.geeksforgeeks.org/coin-change-dp-7/ ). This stack overflow link can be helpful as well. (https://stackoverflow.com/questions/45401847/coin-change-recursive-approach) — Jainik, Feb 05 '19 at 21:15

Bentaye · Accepted Answer · 2019-02-05T23:13:27.127

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();
}

@AnnaLA I changed the algorithm, this looks better now and works — Bentaye, Feb 05 '19 at 21:54
@Bentaye Thank you but it is not working... for n = 7 the result is 1 and not 2. I change the title and the code... if you can take a look pls — AnnaLA, Feb 05 '19 at 21:56
for 6 it returns 2, and for 7 it returns 1. I think that looks correct, why should it return 2 when input is 7? — Bentaye, Feb 05 '19 at 21:59
@AnnaLA I understand, I had a typo in the outputs, I updated the outputs. You can try the code, it works fine — Bentaye, Feb 05 '19 at 22:02
Working well Thank you @Bentaye ... How you could change your code if the numbers are 1 , 3 , 5 , 7 instead of 1 , 5 , 7 (adding 3)? — AnnaLA, Feb 05 '19 at 22:16
Let us [continue this discussion in chat](https://chat.stackoverflow.com/rooms/187957/discussion-between-bentaye-and-annala). — Bentaye, Feb 05 '19 at 23:06

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

1 Answers1