17ms Java Solution Similar to Factor Combination


  • 0
    public class Solution {
        public int smallestFactorization(int num) {
            if (num < 10) return num;
            List<List<Integer>> lists = new ArrayList<>();
            List<Integer> path = new ArrayList<>();
            helper(num, 2, path, lists);
            int res = Integer.MAX_VALUE;
            for (List<Integer> list : lists) {
                int temp = 0;
                boolean flag = true;
                for (int val : list) {
                    if ((Integer.MAX_VALUE - val) / 10 < temp) {
                    	flag = false;
                    	break;
                    }
                    temp = temp * 10 + val;
                }
                if (flag) res = Math.min(res, temp);
            }
            return res == Integer.MAX_VALUE ? 0 : res;
        }
        private void helper(int num, int curr, List<Integer> path, List<List<Integer>> lists) {
            if (num < 10) {
            	path.add(num);
                lists.add(new ArrayList<>(path));
                path.remove(path.size() - 1);
                return;
            }
            for (int i = curr; i < 10; i++) {
                if (num % i == 0 && num / i >= i) {
                    path.add(i);
                    helper(num / i, i, path, lists);
                    path.remove(path.size() - 1);
                }
            }
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.