Find all array subsequences of a given value

Question

I'm looking for an algorithm that given a list like:

[1, 1, 2, 1, 1, 5, 1, 1, 1, 1, 2, 1]

can find and return all subsequences of a given value. For example, if given the value 1, the function would return [[1, 1], [1, 1], [1, 1, 1, 1], [1]].

I believe this is similar to problems such as summing up all subsequences of an array or finding all the subsequences of a given string but algorithms was never my strong suit. The answer can be psuedo-code or language agnostic. And if you wouldn't mind, could you explain the complexity of the solution?

I can explain what I need this for if that helps. Comment if you want that.

Answer 1

We can do this in O(n) time complexity by scanning the array twice. Pseudocode:

//use an array list so we can access element at an index in O(1) time
outputArrays = new ArrayList<int[]> //list of arrays

//loop to declare arrays of outputs - this scans each element once
int currLen = 0;
for (item in inputArray) {
 if (item = itemToLookFor) {
  currLen++;
 }else if (currLen > 0) {
  currLen = 0;
  outputArrays.add(new int[currLen]);
 }
}

//loop to actually populate the output - this scans each element once
currLen = 0;
currIndex = 0;
for (item in inputArray) {
 if (item = itemToLookFor) {
  outputArrays.getElement(currIndex)[currLen] = item;
  currLen++;
 }else if (currLen > 0) {
  currLen = 0;
  currIndex++;
 }
}

Let me know if there is anything i can clarify.