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 this time, 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);
                }
            }

        }
    }

}

All Problems

All Solutions