When solving coding problems, especially in topics like recursion, backtracking, dynamic programming, or strings, you’ll often come across terms like subset, subsequence, and substring. Though they sound similar, they have important differences.

Let’s explore each one with clear definitions, examples, and comparisons.

1️⃣ Subset

A subset is a set is any combination of elements (including the empty set) taken in any order, and without duplication.

Key Features:

• Order doesn't matter.
• Can include zero or more elements.
• All elements must be present in the original set.
• A set with n elements has 2^n subsets.

Example:

Original Set: [1, 2, 3]
Subsets:
[ ], [1], [2], [3],
[1,2], [1,3], [2,3],
[1,2,3]

2️⃣ Subsequence

A subsequence is a sequence derived from the original by deleting some or no elements, without changing the relative order of remaining elements. Unlike substrings, subsequences do not need to be contiguous.

Key Features:

• Elements appear in the same order as original.
• Skipping elements is allowed.
• Not necessarily contiguous.

Example:

Original: [1, 2, 3]
Subsequences:
[ ], [1], [2], [3],
[1,2], [1,3], [2,3],
[1,2,3]

Note: This is the same as subsets for arrays, but not for strings (see below).

For the string "abcde":

"ace" is a valid subsequence (characters appear in the same order, but they are not contiguous).
"bde" is a valid subsequence.
"ab" is a valid subsequence.
"edc" is not a subsequence because the order of characters does not match the original string.

3️⃣ Substring

A substring is a contiguous part of a string or array. This means that all characters of the substring must appear consecutively in the original string and in the same order.

Key Features:

• Elements must be contiguous, meaning no gaps between the characters.
• Must maintain order.
• Cannot skip elements.

Example:

Original: "abc"
Substrings:
"a", "b", "c", 
"ab", "bc",
"abc"

⚠️ "ac" is not a substring of "abc" — not contiguous.