leetcode254 -- Factor Combinations (找到一个数的所有因式分解,不一定是最简单的)

# 小郑之家~

### 题目

input:1
output:[]

input: 37
output: []

input:12
output:
[
[2,6],
[2,2,3],
[3,4]
]

def main(n):

def helper(candidates, target):
res = []
for i in range(len(candidates)):
if candidates[i]>target:
break
if candidates[i]==target:
res.append([candidates[i]])
break
if target%candidates[i]==0:
temp = target/candidates[i]
TT = helper(candidates[i:], temp)
for x in TT:
x.insert(0, candidates[i])
res.append(x)

return res

ret = helper(range(2, n), n)

return ret

if __name__ == '__main__':
import sys
print main(int(sys.argv[1]))
~
~

qiuzhao john$python factor_combination.py 1 [] qiuzhao john$ python factor_combination.py 10
[[2, 5]]
qiuzhao john$python factor_combination.py 100 [[2, 2, 5, 5], [2, 2, 25], [2, 5, 10], [2, 50], [4, 5, 5], [4, 25], [5, 20], [10, 10]] qiuzhao john$ python factor_combination.py 8
[[2, 2, 2], [2, 4]]
qiuzhao john$python factor_combination.py 32 [[2, 2, 2, 2, 2], [2, 2, 2, 4], [2, 2, 8], [2, 4, 4], [2, 16], [4, 8]] qiuzhao john$ python factor_combination.py 35
[[5, 7]]
qiuzhao john$python factor_combination.py 37 [] qiuzhao john$

### 其实用下面这两种方法都是可以的

def helper(candidates, start, target, temp, res):
if target <0:
return
if target ==1 :
res.append(temp[:])
return

for i in range(start, len(candidates)):
# recursive
if target%candidates[i] ==0:
temp.append(candidates[i])
helper(candidates, i, target//candidates[i], temp, res)
del(temp[-1])
def helper2(candidates, target):
res = []
for i in range(len(candidates)):
if candidates[i]>target:
break
if target == candidates[i]:
res.append([candidates[i]])
break

if target % candidates[i]==0:
temp = helper2(candidates[i:], target//candidates[i])
for a in temp:
a.insert(0, candidates[i])
res.append(a)
return res

def main(n):

res = []
helper(list(range(2, n)), 0, n, [], res)
print("res1", res)
print("res2", helper2(list(range(2,n)), n))