LC: Factor Combinations - spiralgo/algorithms GitHub Wiki

Factor Combinations

The Essence:

In this question, there are few thing we aren't allowed to do:

1. The factors don't include the pair {input number, 1}
2. We don't include the duplicate pairs, for example {3,9} and {9,3} by the input 27

For this, one can place the current factors of the number into a stack, and have the number already divided by these. After this, once can also check if there are more factors of this number. If not, one can add the current numbers to the total factor combinations.

To avoid duplicates, one can only look up numbers up to the square root of the number being factorized.

Details:

The algorithm here implements a backtracking strategy. The base is non-divisibility. The current factors should also be simply added. The current factors can be held in a stack, since the backtracking would require them to be "popped" from the current decision chain.