# -*- coding: utf-8 -*-
# ﻿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:
# The length of the given array will not exceed 15.
# The range of integer in the given array is [-100,100].
# The given array may contain duplicates, and two equal integers should also be considered as a special case of
# increasing sequence.
import collections


class Solution(object):
    def findSubsequences(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res, mDic = [[]], collections.defaultdict(int)

        for n in nums:
            start = mDic[n]
            m = len(res)
            mDic[n] = len(res)
            for j in xrange(start, m):
                if not res[j] or n >= res[j][-1]:
                    tmp = res[j][::]
                    tmp.append(n)
                    res.append(tmp)


        return [t for t in res if len(t) > 1]

    def findSubsequences2(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res, mDic = [[]], collections.defaultdict(int)

        for n in nums:
            start = mDic[n]
            m = len(res)
            mDic[n] = len(res)

            res += [res[item] + [n] for item in xrange(start, len(res)) if not res[item] or res[item][-1] <= n]

        return [t for t in res if len(t) > 1]

if __name__ == '__main__':
    print Solution().findSubsequences([4, 6, 7, 7])
    print Solution().findSubsequences2([4, 6, 7, 7])
