Given an integer array, your task is to find all the different possible increasing subsequences of the given array, and the length of an increasing subsequence should be at least 2 .

Example:

Input: [4, 6, 7, 7]Output: [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]]

Note:

1. The length of the given array will not exceed 15.
2. The range of integer in the given array is [-100,100].
3. The given array may contain duplicates, and two equal integers should also be considered as a special case of increasing sequence.

题目含义：给定几个整数，求他们能构造的所有递增子序列

1     void increSubSeq(int[] nums, Set
     
      
       > result, List
       
         tmp, int nextIndex) { 2         if (tmp.size() >= 2) result.add(new LinkedList<>(tmp)); 3         for (int i = nextIndex; i < nums.length; i++) { 4             if (tmp.size() == 0 || nums[i] >= tmp.get(tmp.size()-1)) { 5                 tmp.add(nums[i]); 6                 increSubSeq(nums, result, tmp, i + 1); 7                 tmp.remove(tmp.size()-1);//将nums[nextIndex]弹出，继续下一次dfs。 8             } 9         }10     }11     12     public List
        
         
          > findSubsequences(int[] nums) {13 //        这道题可以采用深度优先搜索的方法解决。假设使用tmp来存储当前考虑的子序列，nextIndex表示tmp中最后一个元素的下标的后一个，14 //        则如果nums[nextIndex]的元素不小于tmp中的最后一个元素，就可以将其增加到tmp中，然后继续处理nextIndex+1处的元素，直到最后一个元素或者元素比最后一个小。15 //        接着返回原始的tmp，将nums[nextIndex]弹出，继续下一次dfs。16         Set
          
           
            > result = new HashSet<>();17 List
            
              tmp = new LinkedList<>();18 increSubSeq(nums, result, tmp, 0);19 return new ArrayList<>(result);20 }
            
           
          
         
        
       
      
     

 

方法二: 时间复杂度不符合要求

1     public List
     
      
       > findSubsequences(int[] nums) { 2         if (nums.length == 0) return new ArrayList<>(); 3         Set
       
        
         > result = new HashSet<>(); 4         List
         
          
           > list = new LinkedList<>(); 5 list.add(new ArrayList<>()); 6 for (int i = 0; i < nums.length;i++) 7 { 8 int size = list.size(); 9 for (int j=0;j
           
             tempList = new ArrayList<>(list.get(j));12 if (tempList.size()>0 && tempList.get(tempList.size()-1) > nums[i]) continue;13 tempList.add(nums[i]);14 list.add(tempList);15 if (tempList.size()>1) result.add(tempList);16 }17 }18 return new ArrayList<>(result);19 }