目录

一、题目内容

二、解题思路

三、代码

一、题目内容

给定一个整型数组, 你的任务是找到所有该数组的递增子序列，递增子序列的长度至少是2。

示例:

输入: [4, 6, 7, 7]

输出: [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]]

说明:

给定数组的长度不会超过15。

数组中的整数范围是 [-100,100]。

给定数组中可能包含重复数字，相等的数字应该被视为递增的一种情况。

二、解题思路

1.回溯法：每一次添加的元素需要和上一个子序列的最后一个元素比较大小，大于等于则加入到新的子序列中去。

2.由于不能出现重复的子序列，因此需要检验子序列是否在之前被回溯过，若被回溯过则跳过（continue）。

三、代码

  

   

    

     

    
    

     

      class Solution:
     
    
   

    

     

    
    

     
 def findSubsequences(self, nums):
     
    
   

    

     

    
    

     

       ans = []
     
    
   

    

     

    
    

     

       n = len(nums)
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 def iter_find(i, sublist, n):
     
    
   

    

     

    
    

     
 if i > n:
     
    
   

    

     

    
    

     
 return
     
    
   

    

     

    
    

     
 if len(sublist) >= 2:
     
    
   

    

     

    
    

     

       ans.append(sublist)
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

       temp = []
     
    
   

    

     

    
    

     
 for index in range(i, n):
     
    
   

    

     

    
    

     
 if nums[index] in temp:
     
    
   

    

     

    
    

     
 continue
     
    
   

    

     

    
    

     

       temp.append(nums[index])
     
    
   

    

     

    
    

     
 if len(sublist) == 0 or nums[index] >= sublist[-1]:
     
    
   

    

     

    
    

     

       iter_find(index + 1, sublist + [nums[index]], n)
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

       iter_find(0, [], n)
     
    
   

    

     

    
    

     
 return ans
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      if __name__ == '__main__':
     
    
   

    

     

    
    

     

       nums = [4,3,2,1]
     
    
   

    

     

    
    

     

       s = Solution()
     
    
   

    

     

    
    

     

       ans = s.findSubsequences(nums)
     
    
   

    

     

    
    

     

       print(ans)
     
    
  
 

文章来源: nickhuang1996.blog.csdn.net，作者：悲恋花丶无心之人，版权归原作者所有，如需转载，请联系作者。

原文链接：nickhuang1996.blog.csdn.net/article/details/108230180