BasicCombination.java

package algorithm.basicMath;

import org.junit.Test;

import static org.hamcrest.CoreMatchers.is;
import static org.junit.Assert.assertThat;

public class BasicCombination {

 /*
 TASK
 n개의 서로 다른 원소 중 r개의 원소를 순서없이 선택하는 방법의 수를 구한다.
 */

 @Test
 public void test() {
 assertThat(getByRecursion(0, 0), is(1));
 assertThat(getByRecursion(1, 0), is(1));
 assertThat(getByRecursion(2, 1), is(2));
 assertThat(getByRecursion(8, 3), is(56));

 assertThat(getByDp(0, 0), is(1));
 assertThat(getByDp(1, 0), is(1));
 assertThat(getByDp(2, 1), is(2));
 assertThat(getByDp(8, 3), is(56));
 }

 public int getByRecursion(int n, int r) {
 if (r == 0 || n == r) {
 return 1;
 }
 return getByRecursion(n - 1, r - 1) + getByRecursion(n - 1, r);
 }

 public int getByDp(int n, int r) {
 int cache[][] = new int[10][10];
 if (r == 0 || n == r) {
 return 1;
 }
 if (cache[n][r] != 0) return cache[n][r];
 return cache[n][r] = getByDp(n - 1, r - 1) + getByDp(n - 1, r);
 }
}