[LeetCode] 254. Factor Combinations

Leck1e 发布于2019-08-16 13:44 / 1256人阅读

Problem

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:

You may assume that n is always positive.
Factors should be greater than 1 and less than n.
Example 1:

Input: 1
Output: []

Example 2:

Input: 37
Output:[]

Example 3:

Input: 12
Output:
[
  [2, 6],
  [2, 2, 3],
  [3, 4]
]

Example 4:

Input: 32
Output:
[
  [2, 16],
  [2, 2, 8],
  [2, 2, 2, 4],
  [2, 2, 2, 2, 2],
  [2, 4, 4],
  [4, 8]
]

Solution

class Solution {
    public List> getFactors(int n) {
        List> res = new ArrayList<>();
        if (n == 1) return res;
        helper(n, 2, new ArrayList<>(), res);
        return res;
    }
    private void helper(int n, int factor, List temp, List> res) {
        if (n == 1 && temp.size() > 1) {
            res.add(new ArrayList<>(temp));
        }
        //i starts from factor, to ensure that all factors equals or larger than 2
        for (int i = factor; i <= n; i++) {
            if (n%i == 0) {
                temp.add(i);
                helper(n/i, i, temp, res);
                temp.remove(temp.size()-1);
            }
        }
    }
}

云服务器 GPU云服务器 Combinations Factor LeetCode LeetCode_String

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/72247.html

Leetcode 相似题只有题号不含代码。

找出string里的单词。 186. Reverse Words in a String II, 434. Number of Segments in a String combination类型题 77. Combinations 39. Combination Sum 40. Combination Sum II 216. Combination Sum III 494. Target S...

StonePanda 2019-08-14 18:01 评论0 收藏0
526. Beautiful Arrangement and 254. Factor Combina

摘要：用的思想，加上题目的特殊意思，来解决问题。如果个数字，有种结果。这里对原题多加了一个输出的要求，代码如下。也是为了去重，两个分解的解法是对称的，乘法对称的重点就是用combination的思想，加上题目的特殊意思，来解决问题。 526 Beautiful Arrangement Suppose you have N integers from 1 to N. We define a ...

I_Am 2019-08-14 18:01 评论0 收藏0
leetcode-93-Restore IP Addresses

摘要：题目描述题目理解将一段字符广度搜索截取，分别有种组合形式，添加限制条件，过滤掉不适合的组合元素。长度，大小，首字母应用如果进行字符串的子元素组合穷举，可以应用。所有的循环，利用到前一个状态，都可以理解为动态规划的一种分支题目描述：Given a string containing only digits, restore it by returning all possible va...

wmui 2019-07-31 11:11 评论0 收藏0
[LeetCode - Backtracking] Combinations

摘要：本题与类似，都是用回溯法。求中个数的不同组合，很明显我们需要注意的就是每个数字只能出现一次，这点与不同。 CombinationsGiven two integers n and k, return all possible combinations of k numbers out of 1 ... n. For example, If n = 4 and k = 2, a solu...

fizz 2019-08-16 10:26 评论0 收藏0
[Leetcode] Letter Combinations of a Phone Number 电

摘要：最新更新请见深度优先搜索复杂度时间空间递归栈空间思路首先建一个表，来映射号码和字母的关系。然后对号码进行深度优先搜索，对于每一位，从表中找出数字对应的字母，这些字母就是本轮搜索的几种可能。 Letter Combinations of a Phone Number 最新更新请见：https://yanjia.me/zh/2019/01/... Given a digit string...

fxp 2019-08-14 12:34 评论0 收藏0