gistfile1.py

import operator
import math
from itertools import permutations
import functools

class Solution(object):
    def getProbability(self, balls):
        """
        :type balls: List[int]
        :rtype: float
        """
        seq_length = sum(balls)
        self.valid = 0

        current = []
        possible = []

        def dfs(i):
            if len(current) == seq_length:
                possible.append(current)

                uniqe_balls_box_1 = len(set(current[:int((seq_length/2))]))
                uniqe_balls_box_2 = len(set(current[int(seq_length/2):]))

                if uniqe_balls_box_1 == uniqe_balls_box_2:
                    self.valid += 1
            else:
                for x in range(len(balls)):
                    if balls[x] != 0:

                        current.append(x + 1)
                        balls[x] -= 1
                        dfs(i + 1)
                        balls[x] += 1
                        current.pop()


        dfs(0)

        expectLen = math.factorial(sum(balls)) / functools.reduce(operator.mul, [math.factorial(i) for i in balls])
        print(expectLen)
        print(len(possible))
        print(self.valid)
        print("Answer")
        print((float(self.valid )/ float(len(possible))))


s = Solution()

balls = [2,1,1] # Answer 0.66667 = 8/12
balls = [1,2,1,2] # Answer 0.60000 = 108 / 180
balls = [3,2,1] # Answer 0.30000 = 18 / 60

s.getProbability(balls)