Say you are given a set of coins such as 4 10¢, 4 5¢, and 4 1¢.

You are asked to place these coins on a 12-hour analog clock face, where the next coin you place must be placed at X hours after the previous coin, where X is the value of the previous coin.

So if you place a 1¢ on 12, the next coin you place goes at 1. If you place a 5¢ on 1, the next coin you place goes at 6. And so on.

How can you maximize the number of coins that can be placed on the clock before the next coin would have to be placed in a slot that is already taken?

I did try backtracking, where in you have the array as say [1,1,1,1,5,5,5,5,10,10,10,10], then using backtracking you can try all possible combinations such that for example:

Coin position c_coin(list or an array)
1 0 1 has 3 values now, 5 has 4, 10 has 4
1 (0+1)=>1. 1 has 2,5 has 4, 10 has 4
5 (1+5)=>6. 1 has 2, 5 has 3,10 has 4
10 (10+6)=.16(16%12=4) 1 has 2,5 has 3,10 has 3
10 (10+4)%12=> 2. 1 has 2,5 has 3, 10 has 2
1 (2+1)=>3 1 has 1,5 has 3,10 has 2
5 (3+5)=>8 1 has 1,5 has 2, 10 has 2
1 (8+1)=>9 1 has 0,5 has 2,10 has 2
10 (10+9)%12=>7 1 has 0,5 has 2,10 has 1
10 (10+7)%12=>5 1 has 0,5 has2,10 has 0.. so on and so forth for the other iterations.

so in the end the position array contains => [0, 1, 6, 4, 2, 3, 8, 9, 7, 5, 10, 1]
order of the coins would be => [1, 5, 10, 10, 1, 5, 1, 10, 10, 5, 1, 5]

so from the algorithm: (coins[i]+position[i-1])%numOfHours will give you the value of the current position, here 12 will give you the position of the clock, so you will have to try for all possible combinations, hence the time complexity would be O(n!).

I tried writing the code in java for this:

List<Set> result = new ArrayList<>();

    public List<Set<Integer>> nickelsOnClock(List<Integer> coins,int numHours){

        if(coins.size()==0||coins==null)return result;

        int[] position = new int[100];

        addCoins(coins,position,numHours,new HashSet<>(),0);

        return result;

    }

    private void addCoins(List<Integer> coins,int[] position,int numHours,Set<Integer> set,int index){

        position[1] = (position[0]+coins.get(1))%numHours;

// Set

        for(int i=1;i<coins.size();i++){

            set.add(position[0]);

            set.add(position[1]);

            for(int j=2;j<position.length;j++){

                System.out.println("set "+set);

               // while(set.size()<numHours) {

                    position[j] = (position[j - 1] + coins.get(i)) % numHours;

                    System.out.println("pos "+position[j]+" pos[j-1] "+position[j-1]+" coins "+coins.get(i));

                    addCoins(coins,position,numHours,set,j+1);

                    coins.remove(coins.size()-1);

                    for(int k:position){
                        System.out.println("k "+k);
                    }

               // }
            }

            result.add(set);

        }

    }
	
	but couldn't get through, can anyone help me out with this, it would be great if someone can come up with a solution or let me know what mistake I am making, I am aware this is a pretty complex but interesting problem.
	

Thanks a ton guys! :)