a+b+c=n 조건을 만족하는 경우의 수

30 Aug 2016

void f(int a1, int a2, int a3) {
  // base
  if (a1+a2+a3 == n) {
      if (visited[a1][a2][a3] == 0) {
          //solution++;
      }
      visited[a1][a2][a3] = 1;
      return;
  }
  f(a1+1, a2, a3);
  f(a1, a2+1, a3);
  f(a1, a2, a3+1);
}

좀더 일반화를 해보자.

a+b+c=3 일 경우, 마지막 c는 a,b가 정해지면 알 수 있다.

a+b=3, a+b=2, a+b=1, a+b=0

a+b=3 은 다시

a=3, a=2, a=1, a=0 으로 분류

a1+a2+a3 …+ ak = n일 때 ( 0 <= ak <= n)

int f(int n, int k) {
    // base
    if (k == 1) {
        return 1;
    }
    int solution = 0;
    for (int i = 0; i <= n; i++) {
        solution += f(n-i, k-1);
    }
    return solution;
}