1. import math
  2. import time
  4. def FindRoad(target: [], m: int):
  5.     def isvalid(result, target):
  6.         temp = result['values']
  7.         base = sorted(target)
  8.         output = sorted([j - i for i in temp for j in temp if j > i])
  9.         for i in range(len(base)):
  10.             if output[i] != base[i]:
  11.                 return False
  12.         return True
  14.     def isvalid2(num, target):
  15.         if num > m:
  16.             return False
  17.         if num not in target:
  18.             return False
  19.         return True
  21.     def dfs(target, result):
  22.         target_dict = {k: 0 for k in target for v in range(len(target))}
  23.         # base case
  24.         if len(result['values']) == length:
  25.             if result['values'][-1] == m:
  26.                 if isvalid(result, target):
  27.                     results.append(result)
  28.                     print(result)
  29.         # make progress
  30.         else:
  31.             for i in range(len(target)):
  32.                 if target_dict[target[i]] == 1:
  33.                     # 同一层次， 该元素已经被选择了
  34.                     continue
  35.                 # 标记为已选元素
  36.                 target_dict[target[i]] = 1
  37.                    b
  38.                 if result['path'][i] == 1:
  39.                     target_dict[target[i]] = 0
  40.                     continue
  41.                 # 可能的下个元素的值
  42.                 temp = result['values'][-1] + target[i]
  43.                 if not isvalid2(temp, target):
  44.                     continue
  46.                 result['values'].append(temp)
  47.                 result['path'][i] = 1
  48.                 dfs(target, result)
  49.                 result['path'][i] = 0
  50.                 result['values'].remove(temp)
  52.     length = int(math.sqrt((2 * len(target) + 1))) + 1
  53.     # 同一层次只做一次相同选择
  54.     results = []
  55.     result = {
  56.         'values': [],
  57.         'path': [0 for i in range(len(target))]
  58.     }
  59.     result['values'].append(0)
  60.     dfs(target, result)
  64. nums = [3, 3, 3, 4, 5, 5, 5, 6, 7, 8, 10, 1, 2, 2, 2]
  65. nums = [1, 2, 2, 2, 3, 3, 3, 3, 4, 5, 5, 5, 6, 7, 8, 8, 10, 10, 11, 12, 13, 13, 15, 15, 16, 18, 18, 21]
  66. t1 = time.process_time()
  67. FindRoad(nums, 21)
  68. t2 = time.process_time()
  69. print(t2-t1)
  70. #

总结

  • 横向的剪枝函数
  • 纵向维护路径