leetcode：254. 因子的组合

题目来源

• leetcode：254-VIP. 因子的组合

题目描述

class Solution {
    
public:
    vector<vector<int>> getFactors(int n){
    
        
    }
};

题目解析

题意

给定一个正整数n，写出所有的因子相乘的形式，而且规定了因子从小到大的顺序排列

思路

• 因为需要列出所有的情况，所以可以用回溯法来解决
• 由于题目中说明了1和n本身不能算其因子，那么可以从2开始遍历到n，如果当前的数i可以被n整除，说明i是n的一个因子，将其存入一位数组 out 中，然后递归调用 n/i，此时不从2开始遍历，而是从i遍历到 n/i
• 停止的条件是当n等于1时，如果此时 out 中有因子，将这个组合存入结果 res 中

class Solution {
    
public:
    vector<vector<int>> getFactors(int n) {
    
        vector<vector<int>> res;
        helper(n, 2, {
    }, res);
        return res;
    }
    void helper(int n, int start, vector<int> out, vector<vector<int>>& res) {
    
        if (n == 1) {
    
            if (out.size() > 1) res.push_back(out);
            return;
        }
        for (int i = start; i <= n; ++i) {
    
            if (n % i != 0) continue;
            out.push_back(i);
            helper(n / i, i, out, res);
            out.pop_back();
        }
    }
};

优化

class Solution {
    
public:
    vector<vector<int>> getFactors(int n) {
    
        vector<vector<int>> res;
        helper(n, 2, {
    }, res);
        return res;
    }
    void helper(int n, int start, vector<int> out, vector<vector<int>> &res) {
    
        for (int i = start; i <= sqrt(n); ++i) {
    
            if (n % i != 0) continue;
            vector<int> new_out = out;
            new_out.push_back(i);
            helper(n / i, i, new_out, res);
            new_out.push_back(n / i);
            res.push_back(new_out);
        }
    }
};