# Simple Python

• First build all increasing subsequences regardless of length, then filter out the too short ones.

``````def findSubsequences(self, nums):
subs = {()}
for num in nums:
subs |= {sub + (num,)
for sub in subs
if not sub or sub[-1] <= num}
return [sub for sub in subs if len(sub) >= 2]``````

• @StefanPochmann Nice, is there a clean way to generate the permutation without using set? To handling duplicates is a little tricky. Thanks

• @zhongyuan9817 I have a post without vector hasher in C++ if you are interested. It just needs to decompose previous results into sections contributed from different array entries, so we can tell if we can append current entry to a previous result without duplication. Actually, handling of duplicates is the primary challenge, in my opinion.

• @zzg_zzm Thanks a lot! I have bookmarked the link, will read later!

• @StefanPochmann That's an elegant solution. I am just wondering what would be the time complexity of this?

• @harshaneel said in Simple Python:

@StefanPochmann That's an elegant solution. I am just wondering what would be the time complexity of this?

I am only speaking in terms of C++ since I am not familiar with Python.

Without consideration of the time complexity of array hasher (not sure how Python handles it by default; C++ coder needs to define their own), the time complexity should be `O(2^N)` in worst case (when given array `nums` itself is increasing without duplicates).

Note that the final result `sub` of `num[i=1:N]` is constructed from the previous result based on `nums[i=1:N-1]`, so each additional new subsequences while looping through `for num in nums` are

1. `[nums[1]]`
2. `[nums[2]]`, `[nums[1], nums[2]]`
3. `[nums[3]]`, `[nums[1], nums[3]]`, `[nums[2], nums[3]]`, `[nums[1], nums[2], nums[3]]`
...

So there are maximum possible `sub[k-1].size+1` new subsequences added when processing `nums[k]`, where `sub[k-1].size` is the number of subsequences previously found. Therefore, the overall number of subsequences is `O(2^N)`.

Since duplicated sequences are not allowed, in my opinion, it might not be trivial for hash set of array to compute hash values. Again, I am not sure how Python handles it. But theoretically, the overall time complexity should be `O(2^N*hasher(N))`, where `hasher(N)` is the hash function on arrays with maximum size `N`.

Therefore, I think the challenging point of this problem is how to handle duplicates of big size data (e.g., arrays). So choice of programming languages could provide convenience here.

• This post is deleted!

• @zzg_zzm Apparently hashing takes linear time, as doubling the size doubles the time:

``````>>> from timeit import timeit
>>> for e in range(15, 25):
seq = tuple(range(2**e))
print timeit(lambda: hash(seq), number=100)

0.0127717597061
0.0276374918723
0.0563326366445
0.160355203111
0.262955346616
0.516837713979
1.08255762105
2.06604952219
4.24153727445
8.48543233365
``````

But you only counted "substrings". The number of subsequences is exponential, O(2^N).

• @StefanPochmann Thanks for the hasher testing. Intuitively, I think it's also `O(N)` which is the size of array.

I have corrected the sequence count in my post. I don't know why I counted as `O(N^2)` before...

• @StefanPochmann said in Simple Python:

return [sub for sub in subs if len(sub) >= 2]

In the last line, sub is a tuple, in my opinion, this should return [(...), (...)],
but actually it turns out to be right format: return [[...], [....]], but why??

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.