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

All Problems

All Solutions