SOURCE

const answer = [];


function getAns(i, s, stack, res) {
    if (i === s.length) {
        answer.push(res.concat(stack.slice().reverse()))
    } else {
        stack.push(s[i]);
        getAns(i + 1, s, stack, res);
        stack.pop();
        if (stack.length) {
            res.push(stack.pop());
            getAns(i, s, stack, res);
            stack.push(res.pop())
        }
    }
}
const in_array = [1, 2, 3, 4, 5]
getAns(0, in_array, [], []);
console.log(answer, answer.length);


function testOut(s, seq) {
    let i = 0, j = 0;
    let stack = [];
    while (j < s.length) {
        if (i === s.length) {
            if (stack[stack.length - 1] !== seq[j]) {
                break;
            }
            stack.pop();
            j++;
        } else {
            if (!stack.length || stack[stack.length - 1] !== seq[j]) {
                stack.push(s[i]);
                i = i + 1;
            } else {
                stack.pop();
                j++;
            }
        }
    }
    if (j < s.length) return false;
    return true
}
// console.log(testOut(in_array, answer[0]));
answer.forEach((ans) => {
    console.log(testOut(in_array, ans));
})