无题250901

K 因数分解

链接：https://leetcode.cn/problems/balanced-k-factor-decomposition/

暴力搜索（DFS)

code

/*** Note: The returned array must be malloced, assume caller calls free().*/
int* ans;
int* path;
int len;
int minDiff;int max_(int x, int y) {return x < y ? y : x;
}int min_(int x, int y) {return x < y ? x : y;
}void dfs(int n, int max, int min, int cnt) {if(cnt == len - 1) {     // 此时直接 n 作为最后一个因子int diff = max_(max, n) - min_(min, n);if(diff < minDiff) {minDiff = diff;path[cnt] = n;memcpy(ans, path, sizeof(int) * len);}return;}for(int i = 1; i <= n; i++) {if(n % i == 0) {     // 可以直接覆盖path[cnt] = i;dfs(n / i, max_(max, i), min_(min, i), cnt + 1);}}
}int* minDifference(int n, int k, int* returnSize) {ans = calloc(k, sizeof(int));path = calloc(k, sizeof(int));len = k;minDiff = INT_MAX;dfs(n, 0, INT_MAX, 0);free(path);*returnSize = k;return ans;   
}