滴滴笔试0928 T1代码分享

递归解法，交卷后看了牛客大佬思路才写出来的，所以不知道会不会超时。
import time
start =time.clock()
n, a, b, c = 50,100,100,100 #示例5,3,4,5结果为10;1,100,100,100 结果为4
visited = set()
count = 0
def dfs(i,a,b,c):
    global visited
    global count
    t = tuple([i,a,b,c])
    if i > n :
        return
    if t in visited:
        return
    else:
        visited.add(t)
    if a+b>c and a+c>b and b+c>a:
        count += 1
        #print(a, b, c)  # 顺序不同算两种
    dfs(i+1,a-i-1,b,c)
    dfs(i+1,a,b-i-1,c)
    dfs(i+1,a,b,c-i-1)
dfs(0,a,b,c)
print(count)

end = time.clock()
print('Running time: %s Seconds'%(end-start)) #50,100,100,100 跑了11秒。100,100,100,100跑了很久