字母组合

题目描述： 由 A,B,C 这3个字母就可以组成许多串。 比如：“A”,“AB”,“ABC”,“ABA”,“AACBB” … 现在，小明正在思考一个问题： 如果有a个A，b个B，c个C 字母，能组成多少个不同的长度为n的串呢？

using namespace std;
const int N = 1e6 + 10;
char s[N];
bool t[N][4];
int n;
int ans;
int a, b, c;
int dfs(int u, int a, int b, int c) {
	if (u > n) {
		ans ++;
//		for(int i = 1; i <= u; i ++)cout <<s[i];
//		cout <<endl;
		return 0;
	}
	for (int i = 1; i <= 3; i ++) {
		if (a != 0 && t[u][1] == false && i == 1) {
			t[u][1] = true;
			dfs(u + 1, a - 1, b, c);
			t[u][1] = false;
		}
		if (b != 0 && t[u][2] == false && i == 2) {
			t[u][2] = true;
			s[u] = 'B';
			dfs(u + 1, a, b - 1, c);
			t[u][2] = false;
		}
		if (c != 0 && t[u][3] == false && i == 3) {
			t[u][3] = true;
			s[u] = 'C';
			dfs(u + 1, a, b, c - 1);
			t[u][3] = false;
		}
	}


}
int main() {

	cin >> a >> b >> c >> n;
	dfs(1, a, b, c);
	cout << ans << endl;
}