给定从1到N，N个整数，每个整数给两次，求出2N个元素的所有组合，满足以下条件:1.从1-N的每个整数必须出现两次2.同一整数之间的距离就是该整数的值？

用python实现以下程序
给定从1到N，N个整数，每个整数给两次，求出2N个元素的所有组合，满足以下条件:
1.从1-N的每个整数必须出现两次
2.同一整数之间的距离就是该整数的值。
问题如下
1.设计状态空间树，描述想法和思路，通过回溯来解决这个问题、
2.在Python中以函数的形式实现该算法:
def twice_distance(n):

本人画了多次tree，但是不是时间复杂度太高就是一直输出的不是最终答案

https://tiku.baidu.com/bigque/question/a86b1491daef5ef7ba0d3c9f

从左往右每个格子依次放每个数 （注意到放了一个数以后第二次出现一定在右边 且位置确定）。 放不下去了就回溯。

状态空间就是放满的前缀

def twice_distance(n):
  init = [0 for i in range(2*n)]
  return find_all(n, init, 0, set())

def find_all(n, arr, next_pos, selected):
  while next_pos < len(arr) and arr[next_pos] != 0:
    next_pos += 1

  if next_pos == len(arr):
    return [arr.copy()]

  ans = []
  for i in range(1, n+1):
    other_pos = next_pos + i + 1
    if not i in selected and other_pos < len(arr) and arr[other_pos] == 0:
      arr[next_pos] = i
      arr[other_pos] = i
      selected.add(i)
      ans += find_all(n, arr, next_pos+1, selected)
      selected.remove(i)
      arr[next_pos] = 0
      arr[other_pos] = 0
  return ans 

print(twice_distance(4))
# [[2, 3, 4, 2, 1, 3, 1, 4], [4, 1, 3, 1, 2, 4, 3, 2]]

如果太慢再考虑优化一下