# 如何输出一个序列所有的子序列
"""
例如  L=[1,2,3,4]
输出 [1],[2],[3],[4],[1,2],[1,3,],[1,4],[2,3],[2,4],[3,4],[1,2,3],[2,3,4]
"""

"""
思路:图的深度搜索思路
例子：{1: [2, 3, 4], 2: [3, 4], 3: [4], 4: []}
如果是length==1，那么把每个值都添加进去
如果大于1，那么就是说，先把节点(1)加进去，然后把它的邻居节点加进去(2)，判断长度后(length与process对比)，如果长度不符合
则继续加入邻居节点(从1出发，到2，然后2的邻居节点有3等等)
"""


def traverse(nums, results=None, length=1):
   if results is None:
      results = list()
   # 如果子序列的长度大于总长度，则直接退出
   # 子序列的话，就不包括自身，判断条件是 >=
   if length >= len(nums):
      return

   # 根据长度不同，需要重新遍历一次树
   for value in nums.keys():
      dfs(nums, results, value, length)
   # 遍历+1长度的子序列
   traverse(nums, results, length + 1)

   return results


def dfs(nums, results, value, length):
   # 如果没有邻居节点则把该节点直接插入
   # 使用的是有向图，所以如果没有指向其他节点的边的话，就称为没有邻居节点吧
   # 做三个判断吧，至于为何要加上 length==1的判断条件，是因为会有很多次对单独一个节点判断，重复累计了
   if (nums.get(value) is None or len(nums.get(value)) == 0) \
         and length == 1:
      results.append([value])
      return
   # 对某节点的邻居节点判断
   for v in nums.get(value):
      # 临时表，存储临时结果
      process = list()
      process.append(value)
      # 对该节点的邻居节点进行判断
      _dfs(nums, v, length, process)
      # 加入结果集中
      if process not in results:
         results.append(process)


def _dfs(nums, v, length, process):
   print('lenght == ', length)
   # 长度判断
   if len(process) >= length:
      return
   process.append(v)
   # 对节点的邻居节点判断
   for vv in nums.get(v):
      # 递归
      _dfs(nums, vv, length, process)


if __name__ == '__main__':
   L = [1, 2, 3, 4]
   nums = dict()
   for index, value in enumerate(L):
      l = []
      for i in range(index + 1, len(L)):
         l.append(L[i])
      nums[value] = l

   print('图形结构--->', nums)

   results = traverse(nums)
   print('打印结果--->', results)

图形结构---> {1: [2, 3, 4], 2: [3, 4], 3: [4], 4: []}
打印结果---> [[1], [2], [3], [4], [1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4], [1, 2, 3], [1, 3, 4], [2, 3, 4]]