Find the count of all possible strings of size n.Each character of the string is either ‘R’, ‘B’ or ‘G’. In the final string there needs to be at least r number of ‘R’, at least b number of ‘B’ and at least g number of ‘G’ (such that r + g + b <= n). 
Example 1:
Input: n = 4, r = 1, g = 1, b = 1
Output: 36 
Explanation: No. of 'R' >= 1, 
No. of ‘G’ >= 1, No. of ‘B’ >= 1 
and (No. of ‘R’) + (No. of ‘B’) 
+ (No. of ‘G’) = n then 
following cases are possible: 
1. RBGR and its 12 permutation 
2. RBGB and its 12 permutation 
3. RBGG and its 12 permutation 
Hence answer is 36.
Example 2:
Input: n = 4, r = 2, g = 0, b = 1
Output: 22
Explanation: No. of 'R' >= 2,
No. of ‘G’ >= 0, No. of ‘B’ >= 1
and (No. of ‘R’) + (No. of ‘B’)
+ (No. of ‘G’) <= n then 
following cases are possible:
1. RRBR and its 4 permutation
2. RRBG and its 12 permutation
3. RRBB and its 6 permutation
Hence answer is 22.
Your Task:  
You dont need to read input or print anything. Complete the function possibleStrings() which takes n, r, g, b as input parameter and returns the count of number of all possible strings..
Expected Time Complexity: O(n^{2})
Expected Auxiliary Space: O(n)
Constraints:
1<= n <=20
1<= r+b+g <=n

Source: geeksforgeeks | Difficulty: EASY
Tags: String algorithms

Combinatorics

Data structures

Starter code: #User function Template for python3
class Solution:
    def possibleStrings(ob, n, r, b, g):
        # code here 

Solutions:
class Solution:

	def possibleStrings(ob, n, r, b, g):
		k1 = n - (r + b + g)

		def fact(a):
			f = 1
			if a == 1 or a == 0:
				return 1
			for i in range(1, a + 1):
				f = f * i
			return f
		s = 0
		for i in range(k1 + 1):
			k = k1 - i
			for j in range(k + 1):
				llm = k - j
				l1 = fact(n) // (fact(r + i) * fact(b + j) * fact(g + llm))
				s = s + l1
		return s


class Solution:

	def possibleStrings(ob, n, r, b, g):
		fact = [0 for i in range(n + 1)]
		fact[0] = 1
		for i in range(1, n + 1, 1):
			fact[i] = fact[i - 1] * i
		left = n - (r + g + b)
		sum = 0
		for i in range(0, left + 1, 1):
			for j in range(0, left - i + 1, 1):
				k = left - (i + j)
				sum = sum + fact[n] / (fact[i + r] * fact[j + b] * fact[k + g])
		return int(sum)


class Solution:

	def possibleStrings(ob, n, red, blue, green):

		def f(num, d1, d2, d3):
			if d1 >= d2 and d1 >= d3:
				r = d1 + 1
				(x, y) = (d2, d3)
			elif d2 >= d3:
				r = d2 + 1
				(x, y) = (d1, d3)
			else:
				r = d3 + 1
				(x, y) = (d1, d2)
			up = d1 = d2 = 1
			for i in range(r, num + 1):
				up *= i
			for i in range(1, max(2, x + 1)):
				d1 *= i
			for i in range(1, max(2, y + 1)):
				d2 *= i
			res = up // d1 // d2
			return res
		x = n - red - blue - green
		ans = 0
		for r in range(x + 1):
			for b in range(x - r + 1):
				ans += f(n, red + r, blue + b, green + x - r - b)
		return ans


class Solution:

	def possibleStrings(ob, n, r, b, g):

		def fact(n):
			ans = 1
			while n > 0:
				ans *= n
				n = n - 1
			return ans
		cnt = 0
		left = n - (r + b + g)
		for i in range(0, left + 1):
			for j in range(0, left - i + 1):
				k = left - (i + j)
				cnt += fact(n) // (fact(r + i) * fact(b + j) * fact(k + g))
		return cnt


import math

class Solution:

	def possibleStrings(ob, n, r, b, g):
		left = n - (r + g + b)
		s = 0
		for j in range(left + 1):
			for k in range(left - j + 1):
				z = left - (j + k)
				s += math.factorial(n) // (math.factorial(r + j) * math.factorial(g + k) * math.factorial(b + z))
		return s


class Solution:

	def possibleStrings(ob, n, r, b, g):
		fact = [0 for i in range(n + 1)]
		fact[0] = 1
		for i in range(1, n + 1, 1):
			fact[i] = fact[i - 1] * i
		left = n - (r + b + g)
		sum = 0
		for i in range(0, left + 1, 1):
			for j in range(0, left - i + 1, 1):
				k = left - (i + j)
				sum = sum + fact[n] // (fact[i + r] * fact[j + b] * fact[k + g])
		return sum
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(n, r, g, b) = input().split()
		n = int(n)
		r = int(r)
		g = int(g)
		b = int(b)
		ob = Solution()
		print(ob.possibleStrings(n, r, b, g))


class Solution:

	def possibleStrings(ob, n, r, b, g):
		fact = [None] * (n + 1)
		fact[0] = 1
		for i in range(1, n + 1):
			fact[i] = i * fact[i - 1]
		leftOver = n - (r + b + g)
		total = 0
		for i in range(0, leftOver + 1):
			for j in range(0, leftOver - i + 1):
				k = leftOver - (i + j)
				total += fact[n] // (fact[r + i] * fact[g + j] * fact[b + k])
		return total
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(n, r, g, b) = input().split()
		n = int(n)
		r = int(r)
		g = int(g)
		b = int(b)
		ob = Solution()
		print(ob.possibleStrings(n, r, b, g))


class Solution:

	def possibleStrings(ob, n, r, b, g):
		permutations_arr = [1]
		fact = 1
		for i in range(1, n + 1):
			fact *= i
			permutations_arr.append(fact)
		total_permutations = 0
		rem_n = n - r - b - g
		for i in range(rem_n + 1):
			for x in range(rem_n - i + 1):
				y = rem_n - i - x
				total_permutations += int(permutations_arr[n] / (permutations_arr[r + i] * permutations_arr[b + x] * permutations_arr[g + y]))
		return total_permutations


def cal_permutations(num):
	permutations = 1
	while num > 1:
		permutations *= num
		num -= 1
	return permutations

class Solution:

	def possibleStrings(ob, n, r, b, g):
		max_permutations = cal_permutations(n)
		arr = []
		total_permutations = 0
		rem_n = n - r - b - g
		for i in range(rem_n):
			temp_r = r + i
			for x in range(rem_n - i):
				temp_b = b + x
				temp_g = g + rem_n - i - x
				red_permutations = cal_permutations(temp_r)
				blue_permutations = cal_permutations(temp_b)
				green_permutations = cal_permutations(temp_g)
				arr.append([temp_r, temp_b, temp_g])
				total_permutations += int(max_permutations / (red_permutations * blue_permutations * green_permutations))
			for x in range(rem_n - i):
				temp_g = g + x
				temp_b = b + rem_n - i - x
				if [temp_r, temp_b, temp_g] in arr:
					continue
				red_permutations = cal_permutations(temp_r)
				blue_permutations = cal_permutations(temp_b)
				green_permutations = cal_permutations(temp_g)
				total_permutations += int(max_permutations / (red_permutations * blue_permutations * green_permutations))
		red_permutations = cal_permutations(r + rem_n)
		blue_permutations = cal_permutations(b)
		green_permutations = cal_permutations(g)
		total_permutations += int(max_permutations / (red_permutations * blue_permutations * green_permutations))
		return total_permutations


class Solution:

	def possibleStrings(ob, n, r, b, g):
		fact = [1] * (n + 1)
		for i in range(1, n + 1):
			fact[i] = fact[i - 1] * i
		left = n - (r + g + b)
		ans = 0
		for i in range(left + 1):
			for j in range(left + 1):
				k = left - (i + j)
				if k >= 0:
					R = r + i
					G = g + j
					B = b + k
					ans += fact[n] // (fact[R] * fact[B] * fact[G])
		return ans


class Solution:

	def possibleStrings(ob, n, r, b, g):
		fac = {}
		fac[0] = 1
		for i in range(1, n + 1):
			fac[i] = i * fac[i - 1]
		remaining = n - r - b - g
		red = blue = green = 0
		ans = 0
		while red < remaining + 1:
			blue = 0
			while blue < remaining + 1 - red:
				green = remaining - red - blue
				ans = ans + fac[n] // (fac[r + red] * fac[b + blue] * fac[g + green])
				blue = blue + 1
			red = red + 1
		return ans


class Solution:

	def possibleStrings(ob, n, r, b, g):
		import math
		number = 0
		extra = n - (r + b + g)
		if extra < 0:
			return 0
		else:
			for i in range(extra + 1):
				for j in range(extra + 1 - i):
					k = extra - i - j
					number += math.factorial(n) // math.factorial(r + i) // math.factorial(b + j) // math.factorial(g + k)
		return number


import math

class Solution:

	def dfs(self, n, r, b, g, d):
		if d.get((r, b, g)) != None:
			return 0
		if r + b + g == n:
			d[r, b, g] = int(math.factorial(n) / (math.factorial(r) * math.factorial(b) * math.factorial(g)))
			return d[r, b, g]
		d[r, b, g] = self.dfs(n, r + 1, b, g, d) + self.dfs(n, r, b + 1, g, d) + self.dfs(n, r, b, g + 1, d)
		return d[r, b, g]

	def possibleStrings(self, n, r, b, g):
		d = dict()
		return self.dfs(n, r, b, g, d)


from math import factorial

class Solution:

	def possibleStrings(ob, n, R, B, G):
		res = 0
		for r in range(R, n + 1):
			for g in range(G, n + 1):
				if n - (r + g) < B:
					continue
				res += factorial(n) // (factorial(r) * factorial(g) * factorial(n - r - g))
		return res


class Solution:

	def possibleStrings(ob, n, r, b, g):
		count = 0
		fac = [1] * (n + 1)
		for i in range(2, n + 1):
			fac[i] = fac[i - 1] * i
		rem = n - r - g - b
		for i in range(rem + 1):
			for j in range(rem + 1 - i):
				k = rem - i - j
				count += fac[n] // (fac[i + r] * fac[j + b] * fac[k + g])
		return count