Welcome to Subscribe On Youtube

Question

Formatted question description: https://leetcode.ca/all/254.html

Numbers can be regarded as the product of their factors.

• For example, 8 = 2 x 2 x 2 = 2 x 4.

Given an integer n, return all possible combinations of its factors. You may return the answer in any order.

Note that the factors should be in the range [2, n - 1].

 

Example 1:

Input: n = 1
Output: []

Example 2:

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

Example 3:

Input: n = 37
Output: []

 

Constraints:

• 1 <= n <= 107

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
• C++
• Python
• Go

• 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);
                  }
              }
  
          }
      }
  
  }
  
  ############
  
  class Solution {
      private List<Integer> t = new ArrayList<>();
      private List<List<Integer>> ans = new ArrayList<>();
  
      public List<List<Integer>> getFactors(int n) {
          dfs(n, 2);
          return ans;
      }
  
      private void dfs(int n, int i) {
          if (!t.isEmpty()) {
              List<Integer> cp = new ArrayList<>(t);
              cp.add(n);
              ans.add(cp);
          }
          for (int j = i; j <= n / j; ++j) {
              if (n % j == 0) {
                  t.add(j);
                  dfs(n / j, j);
                  t.remove(t.size() - 1);
              }
          }
      }
  }
  

• class Solution {
  public:
      vector<vector<int>> getFactors(int n) {
          vector<int> t;
          vector<vector<int>> ans;
          function<void(int, int)> dfs = [&](int n, int i) {
              if (t.size()) {
                  vector<int> cp = t;
                  cp.emplace_back(n);
                  ans.emplace_back(cp);
              }
              for (int j = i; j <= n / j; ++j) {
                  if (n % j == 0) {
                      t.emplace_back(j);
                      dfs(n / j, j);
                      t.pop_back();
                  }
              }
          };
          dfs(n, 2);
          return ans;
      }
  };
  

• class Solution:
    def getFactors(self, n: int) -> List[List[int]]:
      ans = []
  
      def dfs(n: int, s: int, path: List[int]) -> None:
        if n <= 1:
          if len(path) > 1:
            ans.append(path.copy())
          return
  
        # always starting at 2
        for i in range(s, n + 1):
          if n % i == 0:
            path.append(i)
            dfs(n // i, i, path)
            path.pop()
  
      dfs(n, 2, [])  # The smallest factor is 2
      return ans
  
  ############
  
  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()
  
  

• func getFactors(n int) [][]int {
  	t := []int{}
  	ans := [][]int{}
  	var dfs func(n, i int)
  	dfs = func(n, i int) {
  		if len(t) > 0 {
  			cp := make([]int, len(t))
  			copy(cp, t)
  			cp = append(cp, n)
  			ans = append(ans, cp)
  		}
  		for j := i; j <= n/j; j++ {
  			if n%j == 0 {
  				t = append(t, j)
  				dfs(n/j, j)
  				t = t[:len(t)-1]
  			}
  		}
  	}
  	dfs(n, 2)
  	return ans
  }
  

All Problems

All Solutions