2
\$\begingroup\$

I'm solving the coin change problem having target of n and upper bound as n.

Also the maximum number of coins is 10.

For example. if the target is 11. then the possible outcomes are -

11
10,1
9,2
9,1,1
....
....
....
2,1,1,1,1,1,1,1,1,1

So the last iteration having eleven 1's are not allowed as the max coins is 10.

I have written code for solving the problem, but that is too complicated and cumbersome and I think it can be optimized for better performance.

The code as in this link and below:

import java.util.ArrayList;


public class Numbers {

/**
 * @param args the command line arguments
 */
static ArrayList<Integer> list;
static int target;
static boolean bl;
static boolean ex;
static int rpl;
public static void main(String[] args) {

    Numbers nm = new Numbers();
    /*
    nm.list = new ArrayList();        
    new Numbers().test1();
    */
    list = new ArrayList<Integer>();  
    bl = false;
    ex = false;
    target = 24;
    nm.test(24);           
}

public void test(int k) { 
    int r = 0;
    for (int i = k; i>0; i--) {
        if(!ex) {
            if(sum(list) + i > target) {
                test(i-1);
            }
            else if(list.size() == 10) {
                /*
                list.add(target - sum(list));
                printFill(list); */                    
                int p = list.get(0);
                if(p*10>=target) {
                    i = p;
                    list.clear();
                }

            } else {
                list.add(i);                     
                if(sum(list) == target) {
                    printFill(list);
                    if(bl)
                        i = rpl;
                    bl = false;
                } else {                        
                    test(i);
                }                
            }
        } else {
            System.out.print("t");
        }
    }
}

public void printFill(ArrayList lt) {
    int i = 0;
    for ( i = 0; i< lt.size()-1; i ++) {            
        System.out.print(lt.get(i)+",");            
    } 
    System.out.print(lt.get(i));
    System.out.println("");    

    i = list.get(list.size()-1);       
    if(i > 1) {
        list.remove(list.size()-1);
        if(list.size()>0) {
            try {
                while (list.get(list.size()-1) == 1) {
                    list.remove(list.size()-1);
                }
            } catch(Exception e ) { }
            /*if(list.size()==0) {
                System.out.println("test");
                ex = true;
            }*/
        }
    } else if(i == 1 ) {
        try {
            while (list.get(list.size()-1) == 1) {
                list.remove(list.size()-1);
            }
        } catch(Exception e ) { }
        if(list.size()>0) {
            bl = true;
            rpl = list.remove(list.size()-1);               
        } else {
            ex = true;
        }              
    }
}

public int sum(ArrayList<Integer> lt) {
    int k = 0;        
    for ( int i = 0; i< lt.size(); i ++) {            
        k = k + lt.get(i);            
    }        
    return k;
}

public void test1() {        
    for(int i=1; i<= 4; i++) {
        if(!list.contains(i)) {
            list.add(i);
            test1();
            list.remove(list.indexOf(i));
        }
    }
    if(list.size() == 4) 
    {
        for(int i=0; i< 4; i++) {
            System.out.print(list.get(i));
        }
        System.out.println("");
    }
}
}
\$\endgroup\$
2
\$\begingroup\$

I'm really struggling to read your code, but I'm trying to take a crack at it. In the mean time, here are some things about your code in general – not about the algorithm you use.

Static fields. You do not want to use static fields for bl, ex etc. My guess is you added them because you set them in the main method, which is static by definition. static means that bl etc. will be shared by all objects of that class – you do not want that.

The best way to fix this is to initialize the field directly or in a constructor, not externally. In other words, something like private boolean bl = false; will do, or put all the default values in a constructor:

public Numbers() {
    bl = false;
    list = new ArrayList<Integer>();
    // etc.
}

Aside from the static problem, think of code re-usage: someone who just wants to use your Numbers class shouldn't have to care about what bl and ex (etc.) do, so they shouldn't have to initialize them. It's not only inconvenient for another user, but it's also dangerous to let the inner workings of your class at the mercy of the user.


Mixing fields and parameters

Two examples:

public void test(int k) { 
    int r = 0;
    for (int i = k; i>0; i--) { // use of k
        if(!ex) {
            if(sum(list) + i > target) { // use of target
public void printFill(ArrayList lt) {
    int i = 0;
    for ( i = 0; i< lt.size()-1; i ++) {            
        System.out.print(lt.get(i)+","); // use of lt         
    } 
    // ...
    i = list.get(list.size()-1); // use of list

k and target in the first example, lt and list in the second example are the same, and this is very dangerous. You want to either stick with the parameter or the field only, but please avoid using a class field and a parameter interchangeably.

The most important point here is to decide whether to use a parameter or the field. printFill seems to be an important part of your algorithm, so I would personally tend to use the field rather than the parameter here, because the code is so specific that it will hardly be re-usable for something else.

As for test(), I would remove the target field altogether as it's only used interchangeably with the parameter k in test(int k). I don't see much sense in keeping the value after test() returned its result. It is more convenient for a user to do numbers.test(25) than numbers.setTarget(25); numbers.test();.


Further issues. The spacing one is somewhat minor, so please take it with a grain of salt.

  • Naming. Your code is hard to understand because I have no idea what bl stands for. test and test1 also don't hint at what the methods do, either. printFill doesn't fill anything but removes elements from the list.

  • Structure. If you're finding yourself getting lost in your own code, it's probably a good idea to restructure your code a little. Particularly, I would suggest abstracting the printing and "filling" (removing) sections of printFill into individual methods. You generally want methods that have one purpose only, and then you combine them later on.

  • Exception handling. Exception handling is a complex subject and it's hard to keep one's solutions elegant and sensible. The first steps for that are not to catch the general exception Exception but the specific one, and to actually handle it once it occurs. In your case, you're catching some of the type IndexOutOfBoundsException, which can be prevented by doing appropriate checks in your loops.

  • Spacing/coding style. Some people use for (int i = 0; i < 5; i++) {, others for(int i=0; i<5; i++){ (among other variants) – there have always been heated debates about which is the "best way." Regardless of what you prefer, what is important is that you're consequent. This is maybe petty, but I feel that a consequent coding style seems more professional and it shows that care has been put into creating the code. However, that may just be my personal opinion.


Edit. There's one somewhat confusing feat in the code, namely that test() uses recursion but a loop as well. Generally, for clean recursion or looping, one would want to shy away from combinations. This seems to be an efficient solution to output the solutions, since you never store a lot in a list and output as soon as possible. I do believe that this would not be a recommendable approach if one wanted to store the solutions in a list, for instance.

I have split printFill(), I've renamed a lot of the variables and I've put the actual implementation of test() into a private method. A user can call test(24) or test(24, 5) for a maximum of five number in the combination and we'll take care of the rest from there.

As to optimization, look out especially for the line i = mainTarget - sum(list) + 1; which had unnecessary recursion calls, as well as if(ex) { return; } which looped unnecessarily but did nothing previously.

List<Integer> l = new ArrayList<Integer>(); – it is good practice to use an interface type as main type (List) and the implementation type (ArrayList) only for the actual initialization. But that's not a big thing and I think you'll want to care about that a little further down the road. :)

I have added some Javadoc but not consequently to all methods.

import java.util.ArrayList;
import java.util.List;

public class Numbers {
    private List<Integer> list;
    private boolean setNewStart;
    private boolean ex;
    private int newStart;

    public static void main(String[] args) {
        Numbers numbers = new Numbers();
        numbers.test(24);
    }

    public Numbers() {
        list = new ArrayList<Integer>();
        setNewStart = false;
        ex = false;
    }

    /**
     * Outputs all possible combinations for a number
     * @param target The number to compute combinations for
     */
    public void test(int target) {
        list = new ArrayList<Integer>();
        test(target, target, 10);
    }

    /**
     * Outputs all possible combinations for a number
     * @param target The number to compute combinations for
     * @param maxSize The maximum number of numbers for the combination
     */
    public void test(int target, int maxSize) {
        list = new ArrayList<Integer>();
        test(target, target, maxSize);
    }


    private void test(int tempTarget, int mainTarget, int maxSize) { 
        for(int i = tempTarget; i > 0; i--) {
            if(ex) {
                return;
            }

            if(sum(list) + i > mainTarget) {
                // +1 because of the loop's i--
                i = mainTarget - sum(list) + 1;
                continue;
            }
            else if(list.size() >= maxSize) {                  
                int firstElem = list.get(0);
                if(firstElem * maxSize >= mainTarget) {
                    i = firstElem;
                    list.clear();
                }
            }
            else { /* sum(list) + i <= mainTarget && list.size() < maxSize */
                list.add(i);
                if(sum(list) == mainTarget) {
                    printList(list);
                    emptyList();

                    if(setNewStart) {
                        i = newStart;
                        setNewStart = false;
                    }
                } 
                else {                        
                    test(i, mainTarget, maxSize);
                }                
            }
        }
    }

    // Change helper functions to private

    /**
     * Empty the list appropriately to prepare
     * for the next possibility.
     */
    private void emptyList() {
        int lastElem = list.get(list.size()-1);

        if(lastElem > 1) {
            list.remove(list.size()-1);
            // commented out loop as it never happened
        }
        else if(lastElem == 1) {            
            while(list.size() > 0 && list.get(list.size()-1) == 1) {
                list.remove(list.size()-1);
            }

            if(list.size() > 0) {
                setNewStart = true;
                // No -1 because of loop in test()
                newStart = list.remove(list.size()-1);               
            }
            else {
                ex = true;
            }              
        }
    }

    private int sum(List<Integer> list) {
        int sum = 0;        
        for(int i = 0; i < list.size(); i++) {            
            sum = sum + list.get(i);            
        }
        return sum;
    }

    private void printList(List<Integer> list) {
        for(int i = 0; i < list.size()-1; i++) {
            System.out.print(list.get(i) + ",");
        }
        System.out.println(list.get( list.size()-1 ));
    }
}
\$\endgroup\$
  • \$\begingroup\$ A static field means it remains the same accross function calls. So I have reused the bl in the function 'test' and the 'printFill' function. Try removing the static in the bl and it code would not work properly. PrintFill was the method which was started as a function which would print the numbers in the list. The k parameter in the test function is not the same as target as test function is called inside test function, thats recursion.Thanks for all the other suggestions. Highly appreciated \$\endgroup\$ – Pradyut Bhattacharya Jul 3 '14 at 8:41
  • \$\begingroup\$ @PradyutBhattacharya Static fields are shared across all objects of the same class; regular fields will be shared across all function calls within the same object, which is what you want. I've edited my post and added an edited version of the code. I hope this can be helpful to you. \$\endgroup\$ – ljacqu Jul 3 '14 at 9:20
  • \$\begingroup\$ Thats a great edition. Thanks. Do you think a version without the recursion using only loops would be faster than this code. Actally I would be using this code for getting possible combinations of 1 to 255 in which case performance would be a huge bottleneck. \$\endgroup\$ – Pradyut Bhattacharya Jul 3 '14 at 10:04
  • \$\begingroup\$ @PradyutBhattacharya Thanks for the kind comment. I feel that recursion is the way to go for this, but if you feel you could do something nice with loops, no one is standing in the way! \$\endgroup\$ – ljacqu Jul 3 '14 at 10:08
  • \$\begingroup\$ Actually and frankly speaking I m not a researcher or phd so I dont know if loops would be faster than recursion. If you kindly confirm if recursion is better as I think from your last comment it would be great. \$\endgroup\$ – Pradyut Bhattacharya Jul 3 '14 at 10:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.