Question
Formatted question description: https://leetcode.ca/all/254.html
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]
]
Algorithm
Iterate from 2 to n
. If the current number i is divisible by n, it means that i is a factor of n. Store it in a onePath
list, and then recursively call n/i
.
At next recursion, do not traverse from 2. It traverses from i to n/i
, and the condition for stopping is when n is equal to 1, if there is a factor in onePath
at this time, store this combination in the result.
Pitfall
Need to avoid case: n=32, and only 32 in this list, add check
if (onePath.size() > 1)
Code
Java
-
import java.util.ArrayList; import java.util.List; public class Factor_Combinations { public static void main(String[] args) { Factor_Combinations out = new Factor_Combinations(); Solution s = out.new Solution(); System.out.println(s.getFactors(32)); } public class Solution { List<List<Integer>> result = new ArrayList<>(); public List<List<Integer>> getFactors(int n) { if (n <= 3) { return result; } dfs(2, n, new ArrayList<Integer>()); return result; } private void dfs(int start, int target, ArrayList<Integer> onePath) { if (target <= 1) { if (onePath.size() > 1) { // to avoid case: n=32, and only 32 in this list result.add(new ArrayList<Integer>(onePath)); } return; } // start is always 2, can be removed, and hardcode to 2 for (int i = start; i <= target; i++) { // note: <=, eg: i=2, target=2 if (target % i == 0) { onePath.add(i); dfs(i, target / i, onePath); // not i+1, but i => example: 32, then 2,2,2... onePath.remove(onePath.size() - 1); } } } } }
-
Todo
-
class Solution(object): def getFactors(self, n): """ :type n: int :rtype: List[List[int]] """ res = [] self.dfsHelper(n, res, [], 2) return res[1:] def dfsHelper(self, n, res, path, start): if len(path) > 1 and path[-2] > path[-1]: return if n == 1: res.append(path + []) return path.append(n) self.dfsHelper(n / n, res, path, n) path.pop() for i in range(start, int(n ** 0.5) + 1): if n % i == 0: path.append(i) self.dfsHelper(n / i, res, path, i) path.pop()