Increasing Subsequences

题目

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的升序子数组，很明显是要穷举数组中的所有数字，加上题目要找到所有solution，所以可以确定可以使用DFS来实现。

这道题使用DFS时，有两个重要的point要注意：

• 这道题很明显给定的数组不是排好序的，那么怎么去掉重复的子数组呢？

  【Answer】既然数组不是排好序的，那么就不能通过判断相邻的数字是不是相等来去重了，这道题可以借用hashtable来去重，把之前出现的数字放到hashtable里面，如果之后有出现了同样的数字，那么就不用再进行递归操作了

• 在什么地方判断是不是升序呢？

  【Answer】如果在递归外面进行判断，也就是说对path数组进行判断会比较麻烦。所以这道题还是在递归的同时进行判断，也就是说生成的path已经是升序的了。怎么判断呢，就是说只有后面的数字大于前面的那个数字时才调用递归，否则不调用递归函数，这样也节省了运行时间。

class Solution(object):
    def findSubsequences(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        def dfs(nums, startIndex, path, result):
            if len(path) >=2: result.append(path)
            hmap = {}
            for i in range(startIndex, len(nums)):
                if hmap.has_key(nums[i]): continue
                if path == [] or nums[i] >= path[-1]:
                    hmap[nums[i]] = 1
                    dfs(nums, i+1, path+[nums[i]], result)
        result = []
        dfs(nums, 0, [], result)
        return result

源码分析

• 语句‘if len(path) >=2: result.append(path）’中为什么没有用return？

如果使用了return，那么产生的path数组的长度就都为2了，就不能继续产生长度大于2的数组了。

• 在什么情况下调用递归函数呢？

在两种情况下会调用递归函数，第一种情况是第一个数字出现的时候，第二种是当新到的数字不小于path中最后一个数字的时候

if path == [] or nums[i] >= path[-1]