- A subarray is a contiguous part of array and maintains relative ordering of elements. For an array/string of size n, there are
n*(n+1)/2non-empty subarrays/substrings. - A subsequence maintain relative ordering of elements but MAY or MAY NOT be a contiguous part of an array. For a sequence of size n, we can have
2^n-1non-empty sub-sequences in total. - A subset MAY NOT maintain relative ordering of elements and can or cannot be a contiguous part of an array. For a set of size n, we can have (
2^n) sub-sets in total.
caution
Every Subarray is a Subsequence.
Every Subsequence is a Subset.
ehen we find subset of a set we dont take a subset which is a premutation
- example {1,2,3}:
- {2,1} and {1,2} are the same thing that is {2,1} is permutation of {1,2} , so we count it only once
- example {1,2,3}:
To add to this there is usually a confusion with substrings. A substring is exactly the same thing as a subarray but in the context of strings.
Consider an array: array = [1,2,3,4]
- Subarray :
[1,2],[1,2,3]- is continous and maintains relative order of elements - Subsequence:
[1,2,4]- is not continous but maintains relative order of elements - Subset: [1,3,2] - is not continous and does not maintain relative order of elements. All its permutations are also valid but only one set of these permulations can be counted once.