Scribd
Upload
10 views1 page

Subsequence Notes

A subsequence is created by including or excluding elements from a sequence without altering their order, resulting in 2^n possible combinations. The document provides a template code for printing all subsequences and discusses the time and space complexity, which are O(2^n * n) and O(n) respectively. It also introduces a method to stop recursion after printing the first valid subsequence using a boolean return value.

Uploaded by

Fagoon Sharma
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
10 views1 page

Subsequence Notes

A subsequence is created by including or excluding elements from a sequence without altering their order, resulting in 2^n possible combinations. The document provides a template code for printing all subsequences and discusses the time and space complexity, which are O(2^n * n) and O(n) respectively. It also introduces a method to stop recursion after printing the first valid subsequence using a boolean return value.

Uploaded by

Fagoon Sharma
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Printing Subsequences - Notes (Final)

What is a Subsequence?
A subsequence is formed by taking or not taking elements without changing order.
Example: [1,2,3] → [], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]
Total = 2^n

Core Idea
At each index, we have two choices:
1. Take the element
2. Do not take the element

Template Code

def printsubseq(i, n, arr):


if i >= n:
print(arr)
return

[Link](nums[i])
printsubseq(i + 1, n, arr)

[Link]()
printsubseq(i + 1, n, arr)

nums = [1, 2, 3]
printsubseq(0, len(nums), [])

Time Complexity
O(2^n * n)

Space Complexity
O(n)

Stop After Printing First Valid Subsequence (Functional Recursion)

Return boolean to stop recursion early.

def printOneSubseq(i, n, arr):


if i >= n:
print(arr)
return True
else:
# take
[Link](nums[i])
if printOneSubseq(i + 1, n, arr):
return True

# backtrack
[Link]()

# not take
if printOneSubseq(i + 1, n, arr):
return True

return False

nums = [1, 2, 3]
printOneSubseq(0, len(nums), [])

Key Idea: Use boolean return to stop recursion once first subsequence is printed.

You might also like