果家 两轮背靠背

1. def numSquarefulPerms(n):
   
2.     if n == 0:
   
3.         return []
   
4.    
   
5.     visited = [False]*(n+1)
   
6.     graph = {x:[] for x in range(1, n+1)}
   
7.     for i in range(1, n+1):
   
8.         for j in range(1, i):
   
9.             s = i+j
   
10.             if helper(s):
    
11.                 graph[i].append(j)
    
12.                 graph[j].append(i)
    
13. 
    
14.     res = []
    
15.     for x in graph:
    
16.         dfs(graph, visited, n, res, [x], x)
    
17.     return res
    
18. 
    
19. def helper(n):
    
20.     x = n
    
21.     while x*x > n:
    
22.         x = (x+n//x)//2
    
23.     return x*x == n
    
24. 
    
25. def dfs(graph, visited, n, res, path, i):
    
26.     if len(path) == n:
    
27.         res.append(path[:])
    
28.         return
    
29.    
    
30.     visited[i] = True
    
31.     for j in graph[i]:
    
32.         if not visited[j]:
    
33.             dfs(graph, visited, n, res, path + [j], j)
    
34.     visited[i] = False
    
35. 
    
36. for n in range(21):
    
37.     print(n, numSquarefulPerms(n))

复制代码

1. (0, [])
   
2. (1, [[1]])
   
3. (2, [])
   
4. (3, [])
   
5. (4, [])
   
6. (5, [])
   
7. (6, [])
   
8. (7, [])
   
9. (8, [])
   
10. (9, [])
    
11. (10, [])
    
12. (11, [])
    
13. (12, [])
    
14. (13, [])
    
15. (14, [])
    
16. (15, [[8, 1, 15, 10, 6, 3, 13, 12, 4, 5, 11, 14, 2, 7, 9], [9, 7, 2, 14, 11, 5, 4, 12, 13, 3, 6, 10, 15, 1, 8]])
    
17. (16, [[8, 1, 15, 10, 6, 3, 13, 12, 4, 5, 11, 14, 2, 7, 9, 16], [16, 9, 7, 2, 14, 11, 5, 4, 12, 13, 3, 6, 10, 15, 1, 8]])
    
18. (17, [[16, 9, 7, 2, 14, 11, 5, 4, 12, 13, 3, 6, 10, 15, 1, 8, 17], [17, 8, 1, 15, 10, 6, 3, 13, 12, 4, 5, 11, 14, 2, 7, 9, 16]])
    
19. (18, [])
    
20. (19, [])
    
21. (20, [])

复制代码

[/i][/i][/i][/i]

五年后挖坟写一下第一题：

1. def numSquarefulPerms(n):
   
2.     def isSqr(num):
   
3.         x = int(num**0.5)
   
4.         return x * x == num
   
5. 
   
6.     def dfs(curr_path, used):
   
7.         if len(curr_path) == n:
   
8.             ans.append(curr_path[:])
   
9.             return
   
10.         for next_num in range(1, n + 1):
    
11.             if next_num in used or not isSqr(curr_path[-1] + next_num):
    
12.                 continue
    
13.             used.add(next_num)
    
14.             dfs(curr_path + [next_num], used)
    
15.             used.remove(next_num)
    
16. 
    
17.     ans = []
    
18.     for i in range(1, n + 1):
    
19.         dfs([i], {i})
    
20.     return ans

复制代码