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()

254 - Factor Combinations

Question

Algorithm

Pitfall

Code

All Problems

All Solutions