要点：这题是combination的应用，从左向右想比从右向左容易。
- 因为有结果从小到大的要求，暗示用combintion而不是permutation
- 其实就是从小到大验证因子，每个因子和其对称因子立即成为一个res到solutions里
- 因子的范围是i*i<=n，因为对称的部分已经在验证当前因子的时候push到solutions里了
- 每层的循环内从当前因子开始验证，每层要分解的数是上一层分解后剩下的
错误点：
- confusion：每一个因子都有可能，所以是combination
- 与combination稍有不同，每次的push的res是对称的两个因子，而传到下一层的是当前因子。
https://repl.it/CfT5/1 (recursion)
https://repl.it/Cf13/1 (iteration)
- 就是把中间状态存到queue or stack里，然后从里面取出来继续，order对应结果的order，所以无所谓
- 错误点：别忘了n%i的条件
class Solution(object):
def getFactors(self, n):
"""
:type n: int
:rtype: List[List[int]]
"""
def helper(n, start, res, solutions):
while start*start<=n: # error: <=n, not <n
if n%start==0:
solutions.append(res+[start, n/start])
helper(n/start, start, res+[start], solutions)
start+=1
solutions = []
helper(n, 2, [], solutions)
return solutions
sol = Solution()
assert sol.getFactors(12)==[[2,6],[2,2,3],[3,4]]
assert sol.getFactors(4)==[[2,2]]
from collections import deque
class Solution(object):
def getFactors(self, n):
"""
:type n: int
:rtype: List[List[int]]
"""
q = deque([(n, 2, [])])
solutions = []
while q:
n, start, res = q.popleft()
while start*start<=n:
if n%start==0:
solutions.append(res+[start, n/start])
q.append((n/start, start, res+[start]))
start+=1
return solutions