Combination

Definition

$\dbinom{n}{k} = \dbinom{n-1}{k-1} + \dbinom{n-1}{k}$

$\dbinom{n}{k} =1, k=0 \thinspace or\thinspace k=n$

Recursive Implementation (I)

int comb(int n, int k) { 
    if(k == n || k == 0) return 1;
    else return comb(n-1, k-1) + comb(n-1, k);
}

• $T(n) = O(2^n)$

Recursive Implementation (II)

• 因為作法一的複雜度極高，要更有效率，是必要減少 recursive call 的次數。
• 換一個定義去想：

$\dbinom{n}{k} = \dbinom{n}{k-1} \times \dfrac{n-k+1}{k},\thinspace k>0$

$\dbinom{n}{k} = 1, \thinspace k=0$

int comb2(int n, int k) {
    if (k > 0) return comb2(n, k-1) * (n-k+1) / k;
    else return 1;
}

• $T(n) = O(k)$