LeetCode: Factor Combinations

Posted on August 7, 2018July 26, 2020 by braindenny

Factor Combinations

Similar Problems:

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]
]

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

Solution:

// https://code.dennyzhang.com/factor-combinations
// Basic Ideas: backtracking
//
//   Key points: How to avoid duplicates
//
// Complexity: Time ? Space ?
import "math"
func dfs(combination []int, start int, n int, res *[][]int) {
    if (n == 1) && len(combination) > 1 {
        combination2 := make([]int, len(combination))
        copy(combination2, combination)
        *res = append(*res, combination2)
        return
    }

    for i:=start; i<=int(math.Sqrt(float64(n))); i++ {
        if (n%i==0) {
            combination = append(combination, i)
            dfs(combination, i, n/i, res)
            combination = combination[0:len(combination)-1]
        }
    }
    // examine myself
    if len(combination) != 0 {
        combination = append(combination, n)
        dfs(combination, n, 1, res)
        combination = combination[0:len(combination)-1]
    }
}

func getFactors(n int) [][]int {
    res := [][]int{}
    dfs([]int{}, 2, n, &res)
    return res
}

Post Views: 6