Find all increasing subsequences of an array
Given an integer array, find all distinct increasing subsequences of length two or more.
For example,
Input: [2, 4, 5, 4]
Output: [[2, 4, 5], [2, 5], [2, 4], [4, 5]]
Input: [3, 2, 1]
Output: []
Output: [[2, 4, 5], [2, 5], [2, 4], [4, 5]]
Input: [3, 2, 1]
Output: []
We can use backtracking to solve this problem. The idea is to traverse the array from left to right, starting from the next available index, and add the current element to the sequence only if it exceeds the previous element in the sequence. Then recursively explore the remaining elements to check if they will lead to the solution or not. If at any point the sequence has a length of two or more, add it to the result.
Following is the C++, Java, and Python implementation based on the idea:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 |
#include <iostream> #include <vector> using namespace std; void recur(vector<int> const &nums, vector<vector<int>> &result, vector<int> &curr, int start) { // if the current sequence has length of two or more, push it to the result set if (curr.size() >= 2) { vector<int> r(curr.begin(), curr.end()); result.push_back(r); } // start from the next index till the last for (int i = start; i < nums.size(); i++) { // if sequence is empty, or current number is more than the previous number // in the sequence if (curr.empty() || nums[i] > curr.back()) { // append current number to the sequence curr.push_back(nums[i]); // recur for the next index `i+1` recur(nums, result, curr, i + 1); // backtrack: remove current number from the sequence curr.pop_back(); } } } vector<vector<int>> findSubsequences(vector<int> const &nums) { // set to store all subsequences vector<vector<int>> result; // vector to store a subsequence vector<int> curr; // process all integers starting from index 0 recur(nums, result, curr, 0); return result; } int main() { vector<int> nums = {2, 4, 5, 4}; vector<vector<int>> result = findSubsequences(nums); for (auto &row: result) { for (int i: row) { cout << i << ' '; } cout << endl; } return 0; } |
Output:
2 4
2 4 5
2 5
2 4
4 5
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
import java.util.*; class Main { private static void recur(int[] nums, List<List<Integer>> result, Deque<Integer> curr, int start) { // if the current sequence has length of two or more, push it to the result set if (curr.size() >= 2) { result.add(new ArrayList<>(curr)); } // start from the next index till the last for (int i = start; i < nums.length; i++) { // if sequence is empty, or current number is more than the previous number // in the sequence if (curr.isEmpty() || nums[i] > curr.peekLast()) { // append current number to the sequence curr.addLast(nums[i]); // recur for the next index `i+1` recur(nums, result, curr, i + 1); // backtrack: remove current number from the sequence curr.removeLast(); } } } public static List<List<Integer>> findSubsequences(int[] nums) { List<List<Integer>> result = new ArrayList<>(); recur(nums, result, new ArrayDeque<>(), 0); return result; } public static void main(String[] args) { int[] nums = {2, 4, 5, 4}; System.out.println(findSubsequences(nums)); } } |
Output:
[[2, 4], [2, 4, 5], [2, 5], [2, 4], [4, 5]]
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
from collections import deque def recur(nums, result, curr=deque(), start=0): # if the current sequence has length of two or more, push it to the result set if len(curr) >= 2: result.append(list(curr)) # start from the next index till the last for i in range(start, len(nums)): # if sequence is empty, or current number is more than the previous number # in the sequence if not curr or nums[i] > curr[-1]: # append current number to the sequence curr.append(nums[i]) # recur for the next index `i+1` recur(nums, result, curr, i + 1) # backtrack: remove current number from the sequence curr.pop() def findSubsequences(nums): result = [] recur(nums, result) return result if __name__ == '__main__': nums = [2, 4, 5, 4] result = findSubsequences(nums) print(result) |
Output:
[[2, 4], [2, 4, 5], [2, 5], [2, 4], [4, 5]]
Note the duplicate subsequences in the output. To generate only distinct subsequences, we can keep track of the processed elements, and proceed only if the current element is not processed before, and more than the previous element in the sequence. The following program demonstrates it in C++, Java, and Python:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 |
#include <iostream> #include <vector> #include <unordered_set> using namespace std; void recur(vector<int> const &nums, vector<vector<int>> &result, vector<int> &curr, int start) { // if the current sequence has length of two or more, push it to the result if (curr.size() >= 2) { vector<int> r(curr.begin(), curr.end()); result.push_back(r); } // take a set to keep track of the processed elements unordered_set<int> set; // start from the next index till the last for (int i = start; i < nums.size(); i++) { // proceed only if the current element is not processed before and // more than the previous element in the sequence if (set.find(nums[i]) == set.end() && (curr.empty() || nums[i] > curr.back())) { // mark current element as processed set.insert(nums[i]); // include current element to the sequence curr.push_back(nums[i]); // recur for the next index `i+1` recur(nums, result, curr, i + 1); // backtrack: exclude current element from the sequence curr.pop_back(); } } } vector<vector<int>> findSubsequences(vector<int> const &nums) { // vector of vectors to store all subsequences vector<vector<int>> result; // vector to store a subsequence vector<int> curr; // process all elements starting from index 0 recur(nums, result, curr, 0); return result; } int main() { vector<int> nums = {2, 4, 5, 4}; vector<vector<int>> result = findSubsequences(nums); for (vector<int> &row: result) { for (int i: row) { cout << i << ' '; } cout << endl; } return 0; } |
Output:
2 4
2 4 5
2 5
4 5
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
import java.util.*; class Main { private static void recur(int[] nums, List<List<Integer>> result, Deque<Integer> curr, int start) { // if the current sequence has length of two or more, push it to the result if (curr.size() >= 2) { result.add(new ArrayList<>(curr)); } // take a set to keep track of the processed elements Set<Integer> set = new HashSet<>(); // start from the next index till the last for (int i = start; i < nums.length; i++) { // proceed only if the current element is not processed before and // more than the previous element in the sequence if (!set.contains(nums[i]) && (curr.isEmpty() || nums[i] > curr.peekLast())) { // mark current element as processed set.add(nums[i]); // include current element to the sequence curr.addLast(nums[i]); // recur for the next index `i+1` recur(nums, result, curr, i + 1); // backtrack: exclude current element from the sequence curr.removeLast(); } } } public static List<List<Integer>> findSubsequences(int[] nums) { List<List<Integer>> result = new LinkedList<>(); recur(nums, result, new ArrayDeque<>(), 0); return result; } public static void main(String[] args) { int[] nums = {2, 4, 5, 4}; System.out.println(findSubsequences(nums)); } } |
Output:
[[2, 4], [2, 4, 5], [2, 5], [4, 5]]
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
from collections import deque def recur(nums, result, curr=deque(), start=0): # if the current sequence has length of two or more, push it to the result if len(curr) >= 2: result.append(list(curr)) # take a set to keep track of the processed elements s = set() # start from the next index till the last for i in range(start, len(nums)): # proceed only if the current element is not processed before and # more than the previous element in the sequence if nums[i] not in s and (not curr or nums[i] > curr[-1]): # mark current element as processed s.add(nums[i]) # include current element to the sequence curr.append(nums[i]) # recur for the next index `i+1` recur(nums, result, curr, i + 1) # backtrack: exclude current element from the sequence curr.pop() def findSubsequences(nums): result = [] recur(nums, result) return result if __name__ == '__main__': nums = [2, 4, 5, 4] result = findSubsequences(nums) print(result) |
Output:
[[2, 4], [2, 4, 5], [2, 5], [4, 5]]
Here’s alternative solution that avoids the use of set data structure.
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 |
#include <iostream> #include <vector> using namespace std; void recur(vector<int> const &nums, vector<vector<int>> &result, vector<int> &curr, int start) { // if the end of input is reached if (start == nums.size()) { // push the current sequence to the result if its length is two or more if (curr.size() >= 2) { vector<int> r(curr.begin(), curr.end()); result.push_back(r); } return; } // if sequence is empty, or current element is more than the previous element // in the sequence if (curr.empty() || nums[start] > curr.back()) { // include current element in the sequence curr.push_back(nums[start]); // recur for the next index recur(nums, result, curr, start + 1); // backtrack: remove current element from the sequence curr.pop_back(); } // exclude current element only if it is non-repeating if (curr.empty() || nums[start] != curr.back()) { recur(nums, result, curr, start + 1); } } vector<vector<int>> findSubsequences(vector<int> const &nums) { // vector of vectors to store all subsequences vector<vector<int>> result; // vector to store a subsequence vector<int> curr; // process all elements starting from index 0 recur(nums, result, curr, 0); return result; } int main() { vector<int> nums = {2, 4, 5, 4}; vector<vector<int>> result = findSubsequences(nums); for (vector<int> &row: result) { for (int i: row) { cout << i << ' '; } cout << endl; } return 0; } |
Output:
2 4 5
2 5
2 4
4 5
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
import java.util.*; class Main { private static void recur(int[] nums, List<List<Integer>> result, Deque<Integer> curr, int start) { // if the end of input is reached if (start == nums.length) { // push the current sequence to the result if its length is two or more if (curr.size() >= 2) { result.add(new ArrayList<>(curr)); } return; } // if sequence is empty, or current element is more than the previous element // in the sequence if (curr.isEmpty() || nums[start] > curr.peekLast()) { // include current element in the sequence curr.addLast(nums[start]); // recur for the next index recur(nums, result, curr, start + 1); // backtrack: remove current element from the sequence curr.removeLast(); } // exclude current element only if it is non-repeating if (curr.isEmpty() || nums[start] != curr.peekLast()) { recur(nums, result, curr, start + 1); } } public static List<List<Integer>> findSubsequences(int[] nums) { List<List<Integer>> result = new ArrayList<>(); recur(nums, result, new ArrayDeque<>(), 0); return result; } public static void main(String[] args) { int[] nums = {2, 4, 5, 4}; System.out.println(findSubsequences(nums)); } } |
Output:
[[2, 4, 5], [2, 5], [2, 4], [4, 5]]
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
from collections import deque def recur(nums, result, curr=deque(), start=0): # if the end of input is reached if start == len(nums): # push the current sequence to the result if its length is two or more if len(curr) >= 2: result.append(list(curr)) return # if sequence is empty, or current element is more than the previous element # in the sequence if not curr or nums[start] > curr[-1]: # include current element in the sequence curr.append(nums[start]) # recur for the next index recur(nums, result, curr, start + 1) # backtrack: remove current element from the sequence curr.pop() # exclude current element only if it is non-repeating if not curr or nums[start] != curr[-1]: recur(nums, result, curr, start + 1) def findSubsequences(nums): result=[] recur(nums, result) return result if __name__ == '__main__': nums = [2, 4, 5, 4] result = findSubsequences(nums) print(result) |
Output:
[[2, 4, 5], [2, 5], [2, 4], [4, 5]]
The time complexity of all above-discussed methods is exponential and requires additional space for call stack.
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)