[LeetCode] 254. Factor Combinations 因子组合
Numbers can be regarded as product of its factors. For example,
8 = 2 x 2 x 2;
= 2 x 4.
Write a function that takes an integer n and return all possible combinations of its factors.
Note:
- Each combination's factors must be sorted ascending, for example: The factors of 2 and 6 is
[2, 6], not[6, 2]. - You may assume that n is always positive.
- Factors should be greater than 1 and less than n.
Examples:
input: 1
output:
[]
input: 37
output:
[]
input: 12
output:
[
[2, 6],
[2, 2, 3],
[3, 4]
]
input: 32
output:
[
[2, 16],
[2, 2, 8],
[2, 2, 2, 4],
[2, 2, 2, 2, 2],
[2, 4, 4],
[4, 8]
]
Numbers can be regarded as product of its factors. For example,
8 = 2 x 2 x 2;
= 2 x 4.
Write a function that takes an integer n and return all possible combinations of its factors.
Note:
- Each combination's factors must be sorted ascending, for example: The factors of 2 and 6 is
[2, 6], not[6, 2]. - You may assume that n is always positive.
- Factors should be greater than 1 and less than n.
Examples:
input: 1
output:
[]
input: 37
output:
[]
input: 12
output:
[
[2, 6],
[2, 2, 3],
[3, 4]
]
input: 32
output:
[
[2, 16],
[2, 2, 8],
[2, 2, 2, 4],
[2, 2, 2, 2, 2],
[2, 4, 4],
[4, 8]
]
写一个函数，给定一个整数n，返回所有可能的因子组合。
解法：递归。从2开始遍历到sqrt(n)，能被n整除就进下一个递归，当start超过sqrt(n)时，start变成n，进下一个递归。
Java:
public class Solution {
public List<List<Integer>> getFactors(int n) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
helper(result, new ArrayList<Integer>(), n, 2);
return result;
}
public void helper(List<List<Integer>> result, List<Integer> item, int n, int start){
if (n <= 1) {
if (item.size() > 1) {
result.add(new ArrayList<Integer>(item));
}
return;
}
for (int i = start; i * i <= n; ++i) {
if (n % i == 0) {
item.add(i);
helper(result, item, n/i, i);
item.remove(item.size()-1);
}
}
int i = n;
item.add(i);
helper(result, item, 1, i);
item.remove(item.size()-1);
}
}
Python: Time: O(nlogn) Space: O(logn)
class Solution:
# @param {integer} n
# @return {integer[][]}
def getFactors(self, n):
result = []
factors = []
self.getResult(n, result, factors)
return result def getResult(self, n, result, factors):
i = 2 if not factors else factors[-1]
while i <= n / i:
if n % i == 0:
factors.append(i);
factors.append(n / i);
result.append(list(factors));
factors.pop();
self.getResult(n / i, result, factors);
factors.pop()
i += 1
C++:
// Time: O(nlogn) = logn * n^(1/2) * n^(1/4) * ... * 1
// Space: O(logn) // DFS solution.
class Solution {
public:
vector<vector<int>> getFactors(int n) {
vector<vector<int>> result;
vector<int> factors;
getResult(n, &result, &factors);
return result;
} void getResult(const int n, vector<vector<int>> *result, vector<int> *factors) {
for (int i = factors->empty() ? 2 : factors->back(); i <= n / i; ++i) {
if (n % i == 0) {
factors->emplace_back(i);
factors->emplace_back(n / i);
result->emplace_back(*factors);
factors->pop_back();
getResult(n / i, result, factors);
factors->pop_back();
}
}
}
};
类似题目：
[LeetCode] 39. Combination Sum 组合之和
[LeetCode] 40. Combination Sum II 组合之和 II
[LeetCode] 216. Combination Sum III 组合之和 III
[LeetCode] 377. Combination Sum IV 组合之和 IV
All LeetCode Questions List 题目汇总
最新文章
- dos 命令帮助文档chm
- Oracle体系结构详解
- IE9 打不开界面也不报错，只有打开控制台才会显示 - console
- C#基于Socket的简单聊天室实践
- 详细解密FineReport中的报表执行过程
- C Looooops(扩展欧几里得)
- Keil的使用方法 - 常用功能（二）
- ios固定高度禁止惯性滚动
- 使用Fiddler提高前端工作效率 (介绍篇)
- UIKit Animation
- Quartz简单使用
- 浅谈多核CPU、多线程、多进程
- cocos2d-x中的CCScrollView滑动体验不佳
- [Windows Phone] 如何在 Windows Phone 应用程式制作市集搜寻
- javascript IP验证
- Scrum Meeting Alpha - 10
- 下拉框多级联动辅助js，优化您的下拉框
- Hibernate验证器
- asp.net core 系列 11 配置configuration (下)
- Spring Cloud学习笔记-011