在dota的100多個(gè)英雄中惰许，技能最多的無(wú)疑是召喚師席覆，英文叫carl。
召喚師有冰汹买，雷佩伤，火三種球可以選擇，選擇不同的球就可以組合出不同的技能晦毙。把這個(gè)問題抽象一下生巡，就是
有A種球3個(gè)，B種球3個(gè)见妒，C種球3個(gè)孤荣，從這9個(gè)球中選出3個(gè)，問有多少種取法须揣。同一類中的球不做區(qū)分盐股，有如下10種：

AAA
AAB
AAC
ABB
ABC
ACC
BBB
BBC
BCC
CCC

這個(gè)序列明顯是規(guī)律的〕芸ǎ可以使用回溯的方式生成疯汁。代碼如下：

#include <iostream>
 
using namespace std;
 
int main()
{
    int n;
   
    cin >> n;
   
    int* bit = new int[n+1];
 
    for (int i = 0; i <= n; i++)
    {
        bit[i] = 0;
    }
   
    int cur = 0;
    int sum = 0;
   
    while (1)
    {
        bit[cur]++;
 
        if (cur)
        {
           
            if (bit[cur] <= n && n - 1 == cur)
            {
                sum++;       
                cout << bit[0] << " " << bit[1] << " " << bit[2] << endl;
            }
           
            if (bit[cur] > n || n == cur)
            {
                cur--;
            }       
           
            else
            {
                cur++;
 
                bit[cur] = bit[cur-1] - 1;
            }
        }
 
        else
        {
 
            if (bit[cur] > n)
            {
                break;
            }
 
            else
            {
                cur++;
 
                bit[cur] = bit[cur-1] - 1;
            }
        }
 
    }
 
    cout << sum << endl;
}

當(dāng)然了，對(duì)于回溯來說卵酪，時(shí)間復(fù)雜度是很高的幌蚊，輸入為n時(shí)，時(shí)間復(fù)雜度為O(nn)溃卡。當(dāng)n特別大時(shí)溢豆，這種方式顯然效率太低。
有沒有可能從數(shù)學(xué)的角度來求解這個(gè)問題呢…似乎可以用排列組合的方式來完成塑煎。
首先把這個(gè)問題抽象成如下問題沫换。
有N種球臭蚁，每種各N個(gè)最铁，從這N*N個(gè)球中取出N個(gè)讯赏，問有多少種取法。
或者冷尉，有N種球漱挎，每種球正無(wú)限個(gè)，從中取出N個(gè)雀哨，問有多少種方式磕谅。乍看下去，可能這個(gè)問題有些復(fù)雜雾棺，可以把這個(gè)問題進(jìn)行一次拆分膊夹。
從N種球中取…如果只有1種球，從中取出N個(gè)捌浩，那么只有1中方法放刨。
從2種球中取，為了和上一種情況區(qū)分開尸饺，我們保證2種球中每一種至少取了1個(gè)进统，如果能算出這個(gè)值，那么總的種數(shù)如下：

浪听？中的表達(dá)式未知螟碎。
問題轉(zhuǎn)換為怎么從2至n種球中取出n個(gè)，且每種球至少取一個(gè)迹栓。
可以把這個(gè)問題繼續(xù)轉(zhuǎn)換一下掉分。
2種球的時(shí)候，第1種取a個(gè)（0<a<n）迈螟，第2種取n-a個(gè)叉抡。這個(gè)時(shí)候，問題轉(zhuǎn)換成了把n個(gè)相同的球放入2個(gè)不同的筒中答毫，且每個(gè)筒不為空褥民。這兩個(gè)問題的解是一一對(duì)應(yīng)的，因?yàn)槲覀兛梢园?號(hào)筒中的球當(dāng)成第1種球洗搂，2號(hào)筒中的球作為第2種球消返，反之依然，第1種球中取出的放在第一個(gè)筒中耘拇，第2種球中取出的放入第二個(gè)筒中……
現(xiàn)在需要解決怎樣把n個(gè)球放入2至n個(gè)筒中撵颊，且每個(gè)筒不空。
我們還是以2個(gè)筒來示例惫叛，似乎可以這樣：
首先取出兩個(gè)球倡勇，分別放入兩個(gè)筒中，這樣保證了2個(gè)筒一定不空嘉涌，剩下的n-2個(gè)球妻熊，每一個(gè)球有2種選擇夸浅，所以最后的答案是2n-2，對(duì)嗎扔役？
考慮這種情況帆喇，第3個(gè)球放入1號(hào)筒，第4個(gè)球放入2號(hào)筒亿胸；這種情況和坯钦，第3個(gè)球放入2號(hào)筒，第4個(gè)球放入1號(hào)筒侈玄。它們重復(fù)了…….因此這種方式不對(duì)婉刀。
這樣考慮，把n個(gè)球排成一行序仙，那么一共有n-1個(gè)空位路星，在這n-1個(gè)空位中插入一個(gè)分隔符，就把n種球分成了2類……3個(gè)筒時(shí)插入2個(gè)分隔符……….
最后得到這個(gè)式子：

為把n個(gè)球放入i個(gè)筒中诱桂，且每個(gè)筒不空洋丐。
所以最后的結(jié)果為：