Recursively add int array into the list

Given an integer array, add all permutation into the list.
Let's look at an example.
We have int array {1,2,3}, and get all permutation with same length from the array.
Obviously, the answer is {1,2,3} {1,3,2} {2,1,3} {2,3,1} {3,1,2} {3,2,1}.


public int combos(int[] numbers) {
           ArrayList<Square> list = new ArrayList<Square>(100);
           permute(0,numbers,list);
           return list.size();
      }
public void permute(int start, int[] nums, ArrayList<Square> list) {
           int size = nums.length;
           if (start + 1 == size) {
                Square sq = new Square(nums);
                list.add(sq);
           } else {
                for (int i= start; i<size; i++) {
                     int temp = nums[start];
                     nums[start] = nums[i];
                     nums[i] = temp;
                     permute(start + 1, nums, list);
                     temp = nums[i];
                     nums[i] = nums[start];
                     nums[start] = temp;
                }
           }
      }



If we run this code, it will print the same array six times.
That's because when we adding the permutation, we are adding an reference of the same array.

Array:[I@15db9742,1,2,3
Array:[I@15db9742,1,2,3,
Array:[I@15db9742,1,2,3,
Array:[I@15db9742,1,2,3,
Array:[I@15db9742,1,2,3,
Array:[I@15db9742,1,2,3,

We can fix the code like below. We make a copy of the original array, and pass it to permute in else block.

public void permute(int start, int[] nums, ArrayList<Square> list) {
           int size = nums.length;
           if (start + 1 == size) {
                int[] copy1 = nums.clone();
                Square sq = new Square(copy1);
                System.out.println("adding:");
                list.add(sq);
                sq.print();
           } else {
                int[] copy2 = nums.clone();
                for (int i= start; i<size; i++) {
                     int temp = copy2[start];
                     copy2[start] = copy2[i];
                     copy2[i] = temp;
                     permute(start + 1, copy2, list);
                     //temp = nums[i];
                     //nums[i] = nums[start];
                     //nums[start] = temp;
                }
           }
      }


Now, it correctly print the permutation.

Array:[I@15db9742,1,2,3
Array:[I@6d06d69c,1,3,2
Array:[I@7852e922,2,1,3
Array:[I@4e25154f,2,3,1
Array:[I@70dea4e,3,1,2
Array:[I@5c647e05,3,2,1

LargestCircle – TopCoder

LargestCircle – TopCoder SRM 212 Div 2 (3rd problem):

This problem does not require any algorithm to solve, rather it was hard to figure out how to find cells that constitute the circle.
We need to consider all four vertexes in the cell.
Let's look at 4*4 grid for simplicity.

When we defining our cell structure, we have four vertexes in each cell.
Considering (2,2) as the center, look at the cell (0,0). There are four vertexes (0,0),(0,1),(1,0),(1,1).
Let's look at the distance from (2,2) to these four points.
(0,0) ~ 2.8 ( because it is 2 x sqrt(2))
(0,1) ~ 2.2 ( sqrt(5))
(1,0) ~ 2.2 ( sqrt(5))
(1,1) ~ 1.4 ( sqrt(4))
If we want to draw a circle with radius 2, and we observe that the cells were passed onto the circle.
The four points in each cell bounded by between 1 to 3.
More precisely, the distance from center to any points in the cell falls between r - 1 and r + 1, inclusively.
So, we are able to solve this problem with brute-force, from the beginning to the end of the cells.
At each cell, we try all circles we can make, and choose the maximum.

Here is my complete code.


public class LargestCircle {
      public int radius(String[] grid) {
           boolean[][] cells = new boolean[50][50];
           int row = grid.length;
           int col = grid[0].length();
           if (row == 1 || col == 1)
                return 0;
           for (int i=0;i<row;i++) {
                for (int j=0;j<col;j++) {
                     if (grid[i].charAt(j) == '.')
                          cells[i][j] = true;
                }
           }
           int radius = 0;
           for (int i=0;i<row;i++) {
                for (int j=0;j<col;j++) {
                     int temp = getCircle(cells,i,j);
                     if (temp > radius)
                          radius = temp;
                }
           }
           //TODO
           return radius;
      }
      public int getCircle(boolean[][] cells, int x, int y) {
           for (int i=25;i>0;i--) {
                boolean success = true;
                for (int j=x-i;j<x+i;j++) {
                     for (int k=y-i;k<y+i;k++) {
                          // check the boundary
                          if (!checkBoundary(cells,x,y,j,k,i)){
                               success = false;
                               break;
                          }
                     }
                }
                if (success)
                     return i;
           }
           return 0;
      }
      public boolean checkBoundary(boolean[][] cells, int x, int y, int i, int j, int radius) {
     int[] dx = {0,1,1,0};
     int[] dy = {0,0,1,1};
     double[] r_array = new double[4];
     boolean result = true;
     if (i < 0 || j < 0 || i > 49 || j > 49)
       return false;
     for (int m=0;m<4;m++) {
       int xDif = x-(i+dx[m]);
       int yDif = y-(j+dy[m]);
       double r = Math.sqrt(xDif*xDif + yDif*yDif);
       r_array[m] = r;
     }
     boolean allSatisfy = true;
     for (int m=0;m<4;m++) {
       if (r_array[m] < (radius - 1) || r_array[m] > (radius + 1))
         allSatisfy = false;
     }
     if (allSatisfy && !cells[i][j])
       result = false;
     return result;
   }
 }

Find redundant elements in multiple arrays.

Given multiple arrays, find the common entry in them.
For example, given three integer arrays,
{1,3,5,7,9}
{3,8,9}
{2,4,5,7,9}

the answer is {9}, because it exists in all three arrays.
The brute-force way is to O(n^3), if the the size of each array is n.
The better way is to use hashtable.
In Pseudo Code,

Initialize hashtable ( key = number, value=count)
Loop thru all arrays
     If the entry is in hashtable, increase the count.
     else
          insert the entry into hashtable
For Loop hashtable
     if count == number of arrays
          add to result array;
return result array;


     
       

grafixMask - TopCoder

grafixMask - TopCoder SRM 211 Div 1

This problem can be solved by BFS or DFS. I don't see much difference, but I used BFS that uses queue data structure. One thing to consider is to find connected cells that is only in passable point.
In order to find connected cells, I used boolean 2D arrays that saves the state of each cell, and blocked cells.
In Pseudo code,

     Create queue
     while (Check if there is unpainted cell that is not blocked)
          getArea of all neighbors
          add area into linked list
     end while
     array = sort linked list
     return array

Here is my complete code.

 import java.util.*;
 public class grafixMask {
      boolean[][] fill = new boolean[400][600];
      boolean[][] blocked = new boolean[400][600];
      public int[] sortedAreas(String[] retangles) {
           List<Integer> list = new ArrayList<Integer>();
           for (int i=0; i<400; i++) {
                for (int j=0; j<600; j++) {
                     fill[i][j] = false;
                }
           }
           // mark retangles
           markRetangles(retangles);
           ArrayList<Integer> al = new ArrayList<Integer>();
           LinkedList<Node> q = new LinkedList<Node>();      
           while (isLeft(q)) {
                al.add(getArea(q));
           }
           Collections.sort(al);
           int[] ret = new int[al.size()];
           for (int i=0;i<ret.length;i++) {
                ret[i] = al.get(i);
           }
           return ret;
      }
      public void markRetangles(String[] retangles) {
        for (int i=0; i<400; i++) {
                for (int j=0; j<600; j++) {
                     blocked[i][j] = false;
                }
           }
           for (String str : retangles) {
                String[] block = str.split(" ");
                int[] val = new int[4];
                int i = 0;
                for (String idx : block) {
                     val[i++] = Integer.valueOf(idx);  
                }
                for (int j=val[0]; j<=val[2]; j++) {
                     for (int k=val[1]; k<=val[3]; k++) {
                          blocked[j][k] = true;
                     }
                }
           }
      }
      public int getArea(LinkedList<Node> q) {
           int result = 0;
           while (!q.isEmpty()) {
                Node top = q.removeFirst();
                result++;
                int[] dx = {-1,1,0,0};
                int[] dy = {0,0,-1,1};
                for (int k=0;k<4;k++) {
                     int x = top.x + dx[k];
                     int y = top.y + dy[k];
                     if (x>=0 && x <= 399 && y >=0 && y <=599 && !fill[x][y] && !blocked[x][y]) {
                          q.add(new Node(x,y));
                          fill[x][y] = true;
                     }
                }
           }
           return result;
      }
      public boolean isLeft(LinkedList<Node> q) {
           for (int i=0; i<400; i++) {
                for (int j=0; j<600; j++) {
                     if (!fill[i][j] && !blocked[i][j]) {
                          q.add(new Node(i,j));
                          fill[i][j] = true;
                          return true;
                     }
                }
           }
           return false;
      }
      class Node {
           int x,y;
           Node(int x, int y) {
                this.x = x;
                this.y = y;
           }
      }
 }

CaptureThemAll – TopCoder

CaptureThemAll – TopCoder SRM 207 Div 2

This problem can be solved by BFS, and special care about chess rules.
When doing a check game, you can visit the same spot unlimitless  as long as the rules permit.
The Knight can move 8 directions, where the it move 2 position ( horizontal or vertical firest, then move one position to either direction that is perpendicular to the original move.)
So, for this problem, you don't need to check if the knight visited this spot already or not.
Rather, you have to clear the queue when you find a rook or queen, then add the spot into queue, and do the remaining search again. Also, it can only capture either rook or queen in the same move.
In pseudo code,

Create Queue q
Add the position of knight into q
while (queue is not empty) {
     current = pop the queue;
     if the current position is the rook or queen
          capture it, and clear queue.
          add current position to the queue
     if it captured two
           then return the current move
     Add neighbors of current to the queue
}

Here is problem statement.

Harry is playing magical chess. In this version of the game, all pieces move the same way as in regular chess, but players can cast some magical spells. Unfortunately, Harry's opponent, Joe, has captured all of Harry's pieces except one knight; Joe, on the other hand, still has a queen and a rook. The only chance Harry has to win this game is to cast a spell, "Haste", that will allow Harry's knight to make several moves in a row. You should determine the minimal number of moves the knight needs to capture both the rook and the queen, assuming neither of them moves. You may capture them in either order - rook first or queen first.  You will be given a String, knight, containing information about the knight. You will also be given a String, queen, and a String, rook, giving you information about Joe's pieces. knight, rook and queen will be formatted as "cr", where c is a character between 'a' and 'h', inclusive, determining the column on the board ('a' is the first column, 'h' is the last), and r is a digit between '1' and '8', inclusive, determining the row (1 is the lowest, 8 is the highest).

Here is my code written, and passed all tests.

import java.util.LinkedList;

public class CaptureThemAll {
public int fastKnight(String knight, String rook, String queen) {
boolean[][] joe = new boolean[8][8];
<8 i="" p=""><8 j="" p="">
int hx = Integer.valueOf(knight.substring(1))-1;
int hy = knight.charAt(0) - 'a';
joe[Integer.valueOf(rook.substring(1))-1][rook.charAt(0) - 'a'] = true;
joe[Integer.valueOf(queen.substring(1))-1][queen.charAt(0) - 'a'] = true;

LinkedList queue = new LinkedList();
queue.add(new Harry(hx,hy,0));
int[] captured = new int[4];

while (queue.size() > 0) {
Harry current = queue.removeFirst();
if (capture(current, joe, captured)) {
if (captured[0] != 1) {
captured[0] = 1;
captured[1] = current.move;
queue.clear();
queue.add(new Harry(current.x,current.y,current.move));
} else {
captured[2] = 1;
captured[3] = current.move;
}

}
if (captured[0] == 1 && captured[2] == 1)
return current.move;
addNeighbors(queue, current);
}

return -1;
}

public boolean capture(Harry harry, boolean[][] joe, int[] captured) {
if (joe[harry.x][harry.y]){
// only capture one in the same neighbors
if (!(captured[0] == 1 && captured[1] == harry.move)) {
joe[harry.x][harry.y] = false;
return true;
}
}

return false;
}

public void addNeighbors(LinkedList queue, Harry current) {
int[] dx = {-2,-2,2,2,-1,1,-1,1};
int[] dy = {-1,1,-1,1,-2,-2,2,2};
for (int i=0;i<8 i="" p=""> int x = current.x + dx[i];
int y = current.y + dy[i];
if (x >=0 && y >= 0 && x < 8 && y <8 br=""> queue.add(new Harry(x,y,current.move + 1));
}
}
}

class Harry{
int x;
int y;
int move;
public Harry(int xx, int yy, int m) {
x = xx;
y = yy;
move = m;
}
}

}

SmartWordToy – TopCoder

SmartWordToy, TopCoder SRM 233 Div 1

This problem is not hard to understand. You can use BFS for this problem.
Let's briefly talk about what BFS is.
It is traversing technique in Graph theory. It traverse by breadth first, i.e., start with one node, and traverse all its immediate neighbor nodes, and so on.

In this tree, BFS will traverse 1-2-3-4-5-6-7.

Let's look at more complex example in topcoder.

Problem Statement
   
The toy company "I Can't Believe It Works!" has hired you to help develop educational toys. The current project is a word toy that displays four letters at all times. Below each letter are two buttons that cause the letter above to change to the previous or next letter in alphabetical order. So, with one click of a button the letter 'c' can be changed to a 'b' or a 'd'. The alphabet is circular, so for example an 'a' can become a 'z' or a 'b' with one click.  In order to test the toy, you would like to know if a word can be reached from some starting word, given one or more constraints. A constraint defines a set of forbidden words that can never be displayed by the toy. Each constraint is formatted like "X X X X", where each X is a string of lowercase letters. A word is defined by a constraint if the ith letter of the word is contained in the ith X of the contraint. For example, the constraint "lf a tc e" defines the words "late", "fate", "lace" and "face".  You will be given a String start, a String finish, and a String[] forbid. Calculate and return the minimum number of button presses required for the toy to show the word finish if the toy was originally showing the word start. Remember, the toy must never show a forbidden word. If it is impossible for the toy to ever show the desired word, return -1.

The key is to use BFS, and create huge array to save whether the state is already visited.
Also, forbidden has to saved into array so that when you compare every state, it doesn't compare every forbidden list every time.

Here is the code I wrote. It passed all of test cases.

import java.util.LinkedList;

public class SmartWordToy {
public int minPresses(String start, String finish, String[] forbid) {
boolean[][][][] steps = new boolean[26][26][26][26];
boolean[][][][] forbidden = new boolean[26][26][26][26];
State st = new State(start.charAt(0),start.charAt(1),start.charAt(2),start.charAt(3),0);
State fi = new State(finish.charAt(0),finish.charAt(1),finish.charAt(2),finish.charAt(3),0);
LinkedList forb = new LinkedList();
for (int i=0;i    String[] sp = forbid[i].split(" ");
   char[] ch1 = sp[0].toCharArray();
   char[] ch2 = sp[1].toCharArray();
   char[] ch3 = sp[2].toCharArray();
   char[] ch4 = sp[3].toCharArray();
   for (int j=0;j for (int k=0;k for (int m=0;m for (int n=0;n    if (!forbidden[ch1[j]-'a'][ch2[k]-'a'][ch3[m]-'a'][ch4[n]-'a']) {
    forbidden[ch1[j]-'a'][ch2[k]-'a'][ch3[m]-'a'][ch4[n]-'a'] = true;
forb.add(new State(ch1[j],ch2[k],ch3[m],ch4[n],0));
}
}
}
}
}
}

LinkedList q = new LinkedList();
q.add(st);
steps[st.a-'a'][st.b-'a'][st.c-'a'][st.d-'a'] = true;
while (q.size() > 0) {
State state = q.removeFirst();
if (state.equal(fi))
return state.step;
addNeighbors(state,forbidden,q,steps);
}

return -1;
}

public void addNeighbors(State state, boolean[][][][] forbidden, LinkedList q, boolean[][][][] steps) {
char[] chars = new char[4];
State temp = new State(nextCh(state.a),state.b,state.c,state.d, state.step + 1);

if (canAddtoNeighbor(temp,forbidden,steps)) {
q.add(temp);
steps[temp.a-'a'][temp.b-'a'][temp.c-'a'][temp.d-'a'] = true;
}
temp = new State(prevCh(state.a),state.b,state.c,state.d, state.step + 1);
if (canAddtoNeighbor(temp,forbidden,steps)) {
q.add(temp);
steps[temp.a-'a'][temp.b-'a'][temp.c-'a'][temp.d-'a'] = true;
}
temp = new State(state.a,nextCh(state.b),state.c,state.d, state.step + 1);
if (canAddtoNeighbor(temp,forbidden,steps)) {
q.add(temp);
steps[temp.a-'a'][temp.b-'a'][temp.c-'a'][temp.d-'a'] = true;
}
temp = new State(state.a,prevCh(state.b),state.c,state.d, state.step + 1);
if (canAddtoNeighbor(temp,forbidden,steps)) {
q.add(temp);
steps[temp.a-'a'][temp.b-'a'][temp.c-'a'][temp.d-'a'] = true;
}
temp = new State(state.a,state.b,nextCh(state.c),state.d, state.step + 1);
if (canAddtoNeighbor(temp,forbidden,steps)) {
q.add(temp);
steps[temp.a-'a'][temp.b-'a'][temp.c-'a'][temp.d-'a'] = true;
}
temp = new State(state.a,state.b,prevCh(state.c),state.d, state.step + 1);
if (canAddtoNeighbor(temp,forbidden,steps)) {
q.add(temp);
steps[temp.a-'a'][temp.b-'a'][temp.c-'a'][temp.d-'a'] = true;
}
temp = new State(state.a,state.b,state.c,nextCh(state.d), state.step + 1);
if (canAddtoNeighbor(temp,forbidden,steps)) {
q.add(temp);
steps[temp.a-'a'][temp.b-'a'][temp.c-'a'][temp.d-'a'] = true;
}
temp = new State(state.a,state.b,state.c,prevCh(state.d), state.step + 1);
if (canAddtoNeighbor(temp,forbidden,steps)) {
q.add(temp);
steps[temp.a-'a'][temp.b-'a'][temp.c-'a'][temp.d-'a'] = true;
}
}

public boolean canAddtoNeighbor(State state, boolean[][][][] forbidden, boolean[][][][] steps) {
if (!steps[state.a-'a'][state.b-'a'][state.c-'a'][state.d-'a'] && !forbidden[state.a-'a'][state.b-'a'][state.c-'a'][state.d-'a']){
return true;
}
return false;
}

public char nextCh(char ch) {
   if (ch == 'z')
    return 'a';
return (char)(ch + 1);
}

public char prevCh(char ch) {
if (ch == 'a')
return 'z';
return (char)(ch - 1);
}

class State {
char a;
char b;
char c;
char d;
int step;
public State(char aa, char bb, char cc, char dd, int s) {
a = aa;
b = bb;
c = cc;
d = dd;
step = s;
}

public boolean equal(State s) {
if (a == s.a && b == s.b && c == s.c && d == s.d)
return true;
return false;
}

public void print() {
System.out.println("State:" + a + "," + b + "," + c + "," + d + ",step:" + step);
}
}
}

Comparable Interface

There is a situation you need to sort your Object. You can implement Comparable interface in your class.
Let's take a example.
The Country has String type name, int type gold, silver, bronze. This class represent how many medal each country get in the Olympic games. We need sort this by gold in descending order. If the the number of gold medal is the same, by silver. If the number of silver medal is the same, by bronze.
If all three medals have equal number each, then order by country name in ascending order.


int compareTo(T o)
Compares this object with the specified object for order. Returns a negative integer, zero, or a positive integer as this object is less than, equal to, or greater than the specified object.

In our case, we need to sort by descending in medal count, and ascending in country name.
Based on the requirement, it has to be adjusted.

class Country implements Comparable{
public String name;
public int gold;
public int silver;
public int bronze;
public Country(String n, int g, int s, int b) {
name = n;
gold = g;
silver = s;
bronze = b;
}

// ascending order
public int compareTo(Object o) {
   Country co = (Country)o;
if (this.gold == co.gold) {
if (this.silver == co.silver) {
if (this.bronze == co.bronze) {
return this.name.compareTo(co.name);
} else if (this.bronze > co.bronze)
return -1;
else
return 1;
} else if (this.silver > co.silver)
return -1;
else
return 1;
} else if (this.gold > co.gold) {
return -1;
} else
   return 1;
}
}

public class MyCode {
     public static void main (String[] args) throws java.lang.Exception {
            ArrayList array = new ArrayList(10);
            MyCode code = new MyCode();
            code.create(array);
       
            Collections.sort(array);
            for (int i=0;i                 Country con = array.get(i);
                 System.out.println(con.name + " " + con.gold + " " + con.silver + " " + con.bronze);
           }  
     }
   
     public void create(ArrayList array) {
        array.add(new Country("KOR", 3,1,1));
        array.add(new Country("AUS", 2,1,1));
        array.add(new Country("GRE", 0,0,1));
        array.add(new Country("ZEN", 0,0,1));
        array.add(new Country("ENG", 0,0,1));
    }
   
}

It will print the output below.

KOR 3 1 1
AUS 2 1 1
ENG 0 0 1
GRE 0 0 1
ZEN 0 0 1

Get subset of a String

Given a String, find all subset of the String.
Let's take a example for this.
String s = "abc", and subset we are looking for is
{"a","b","c","ab","ac","bc","abc"}
The number of subset is 2^n - 1, where n is the length of a string.
If we include empty subset, it will be just 2^n.

The first obvious way is to use recursion.
public void subsets(String s, ArrayList subset){
        if(word.length() == 1){
            subset.add(s);
            return;
        }
        else {
            String first = s.substring(0,1);
            String right = s.substring(1);
            subsets(right, subset);
            int size = subset.size();
            for (int i = 0; i < size; i++){
                String temp = first + subset.get(i);
                subset.add(temp);
            }
            subset.add(first);
            return;
        }
    }

Without recursion, we need to think about how the subset is formed.
When something is linked to 2^n, it means there are two possible choices in every n locations.
So, we have binary string with length n. When the bit at the position i is 1, we need to add the character at i to the subset element.
Let's look at the example above.
If the length of string is 3, we have binary string with length 3.

000 -> empty string
001 --> c
010 --> b
100 --> a
101 --> ac
110 --> ab
011 --> bc
111 --> abc

public void subsets(String s) {
       int len = s.length();
       for (int i=1; i< power(2,len);i++) {
            //int j = i << 1;
            for (int j=0;j<3 j="" p="">                if ((i & (1<                    System.out.print(s.charAt(j) + " ");
                }
            }
            System.out.println();
        }
}

Given array and n, get an index from circular array

When there is an array that indexed from 0, it count from 0 as 1, 1 as 2, and so forth. When it reaches the end of the array, it goes to the first again to count.
Given a string array and integer n, return the index of array that count to n.
Let's look at some examples.

Array: {a,b,c,d,e,f}
n: 6
if we start with a, then it return 5 ( because f is at index 5)

n: 20
if we start with a, then it return 1 ( because b is at index 1)

So, the index we are looking is (start + (n - 1)) % (size of array);
start 0, n=6, (0+5) %  6 = 5
start 0, n=20, (0+19)% 6 = 1

BigInteger

There is a situation when long primitive type does not allow to store very large value. There is a Java Class that support a large value, BigInteger.

This class does not support usual mathematical operation, so be careful when use it.
One example is to add or multiply instead of + or *.

Combination & Permutation

This topic is sometimes confusing when we face them in programming. Here, I am giving some insight that you can remember later.

Permutations ( order does matter)

There are two types:

• Repetition is allowed: examples is like "333".
• Repetition is NOT allowed: examples is "123"

1. Permutation with Repetition
When there n different entities, we can have n choices every draw.
For example, choosing 5 of those items, it has n^5 times choices. ( n x n x n x n x n )

In general, it is represented as n^r, where n is the number of items, and choose r of them.

2. Permutation with NO Repetition
Since there is no repetition is allowed, every draw is reduced by 1.
For example, when there are five different balls with color, you have to choose three of them.
First, you draw blue ball, you cannot draw blue ball again.
In this case, the possible choices are 5 x 4 x 3, because you just choose three from five.
In general, when you draw r from n different items, it is represented by

n!/(n-r)!

Combinations ( order does not matter)

There are two types:

• Repetition is allowed: examples is like (3,3,3,10,10).
• Repetition is NOT allowed: examples is (3,4,5,6,10).

1. Combination with No Repetition

Let's take some example.

When we take 3 out of 5 different items that matters order, it is 5!/(5-3)!.

We have balls number from 1 to 5, and choose balls 1,2, and 3.

There are 6 cases that matter order, and just one case that does not matter order.

Permutation have 3! ( 3x2x1) more times than combination.

In general, when we select r from n items, permutation has r! times more than combination.

So, the formula would be n!/r!(n-r)!.

2. Combination with Repetition

This is little confusing category.

Let's look at the example above.

When we take 3 balls from 5 balls (numbered 1 to 5), we are allowed to draw like (3,3,3).

There are three spots, then we can choose three 3, and none of others (1,2,4,5).

XX333XX

In general, we have r + (n-1) balls and want to choose r of them.

(r+n-1)!/r!(n-1)!