Instead of unfolding the full combination tree and storing all possibilities there is a simpler
way to hack this problem.

Result:
O(1) for Next/Previous paths
O(N) for generating larger intervals of the combination tree. Assuming the user would like to display a groups of branches of the combination tree on the UI then a tree would be drawn and branch highlighted using Canvas or SVG/CSS.

Logic

We know that in a nxn grid, there must be n-1 down moves and n-1 right moves.
Then:
(n-1)+(n-1) === 2(n-1)

We are assuming that the order of combinations (paths) doesn't matter.
For instance, a 3x3 grid will have a binary sequence with a maximum of 4 binary digits or steps:
2(n-1)
=2(3-1)
=4
Thus, 4 steps.

All possibilities in an 3x3 grid:

Binary Decimal
0011 3
0101 5
0110 6
1001 9
1010 10
1100 12

Proposal

From the pattern above we know that there must be two 0s and two '1s' in each sequence of steps.
An algorithm could be written to iterate over all binary possibilities with these conditions without having to store each path independently. If there are 1 billion combinations, use an index to increment/decrement or for larger sets split the binary intervals into buckets and iterate over smaller intervals that can be handled by the data type. In JavaScript the max integer is 2^53-1, so use a BigNum library to avoid overflow.

From sequence 1010 to 1100 there is 1 in between that does not meet the requirements (1011) and that sequence will be ignored, thus 1 lost cycle in a while loop.

Psuedo Code

gridSize = 3; // 3x3 grid
maxValue = 15 // maximum binary value '1111'
digitsAllowed = 4 // maximum of four binary digits

for (i = 1; i <= maxValue; i++) {
if (isValid(numToBinary(i), digitsAllowed ) {
// store
} else {
// next
}
}

isValid(n, digitsAllowed) {
// count the number of 1s and 0s
// int nOnes
// int nZeros
if ((digitsAllowed-2)=== (nOnes-1) + (nZeros-1)) {
return true
} else {
return false
}
}