Balanced K-Factor Decomposition solution and explanation

mx = 10**5 + 1
g = [[] for _ in range(mx)]
for i in range(1, mx):
    for j in range(i, mx, i):
        g[j].append(i)


class Solution:
    def minDifference(self, n: int, k: int) -> List[int]:
        def dfs(i: int, x: int, mi: int, mx: int):
            if i == 0:
                nonlocal cur, ans
                d = max(mx, x) - min(mi, x)
                if d < cur:
                    cur = d
                    path[i] = x
                    ans = path[:]
                return
            for y in g[x]:
                path[i] = y
                dfs(i - 1, x // y, min(mi, y), max(mx, y))

        ans = None
        path = [0] * k
        cur = inf
        dfs(k - 1, n, inf, 0)
        return ans

class Solution {
    static final int MX = 100_001;
    static List<Integer>[] g = new ArrayList[MX];

    static {
        for (int i = 0; i < MX; i++) {
            g[i] = new ArrayList<>();
        }
        for (int i = 1; i < MX; i++) {
            for (int j = i; j < MX; j += i) {
                g[j].add(i);
            }
        }
    }

    private int cur;
    private int[] ans;
    private int[] path;

    public int[] minDifference(int n, int k) {
        cur = Integer.MAX_VALUE;
        ans = null;
        path = new int[k];
        dfs(k - 1, n, Integer.MAX_VALUE, 0);
        return ans;
    }

    private void dfs(int i, int x, int mi, int mx) {
        if (i == 0) {
            int d = Math.max(mx, x) - Math.min(mi, x);
            if (d < cur) {
                cur = d;
                path[i] = x;
                ans = path.clone();
            }
            return;
        }
        for (int y : g[x]) {
            path[i] = y;
            dfs(i - 1, x / y, Math.min(mi, y), Math.max(mx, y));
        }
    }
}

class Solution {
public:
    static const int MX = 100001;
    static vector<vector<int>> g;

    vector<int> ans;
    vector<int> path;
    int cur;

    vector<int> minDifference(int n, int k) {
        if (g.empty()) {
            g.resize(MX);
            for (int i = 1; i < MX; i++) {
                for (int j = i; j < MX; j += i) {
                    g[j].push_back(i);
                }
            }
        }

        cur = INT_MAX;
        ans.clear();
        path.assign(k, 0);

        dfs(k - 1, n, INT_MAX, 0);
        return ans;
    }

private:
    void dfs(int i, int x, int mi, int mx) {
        if (i == 0) {
            int d = max(mx, x) - min(mi, x);
            if (d < cur) {
                cur = d;
                path[i] = x;
                ans = path;
            }
            return;
        }
        for (int y : g[x]) {
            path[i] = y;
            dfs(i - 1, x / y, min(mi, y), max(mx, y));
        }
    }
};

vector<vector<int>> Solution::g;

const MX = 100001;
const g: number[][] = Array.from({ length: MX }, () => []);
for (let i = 1; i < MX; i++) {
    for (let j = i; j < MX; j += i) {
        g[j].push(i);
    }
}

function minDifference(n: number, k: number): number[] {
    let cur = Number.MAX_SAFE_INTEGER;
    let ans: number[] | null = null;
    const path: number[] = Array(k).fill(0);

    function dfs(i: number, x: number, mi: number, mx: number): void {
        if (i === 0) {
            const d = Math.max(mx, x) - Math.min(mi, x);
            if (d < cur) {
                cur = d;
                path[i] = x;
                ans = [...path];
            }
            return;
        }
        for (const y of g[x]) {
            path[i] = y;
            dfs(i - 1, Math.floor(x / y), Math.min(mi, y), Math.max(mx, y));
        }
    }

    dfs(k - 1, n, Number.MAX_SAFE_INTEGER, 0);
    return ans ?? [];
}

const MX = 100001

var g [][]int

func init() {
	g = make([][]int, MX)
	for i := 1; i < MX; i++ {
		for j := i; j < MX; j += i {
			g[j] = append(g[j], i)
		}
	}
}

var (
	cur  int
	ans  []int
	path []int
)

func minDifference(n int, k int) []int {
	cur = math.MaxInt32
	ans = nil
	path = make([]int, k)
	dfs(k-1, n, math.MaxInt32, 0)
	return ans
}

func dfs(i, x, mi, mx int) {
	if i == 0 {
		d := max(mx, x) - min(mi, x)
		if d < cur {
			cur = d
			path[i] = x
			ans = slices.Clone(path)
		}
		return
	}
	for _, y := range g[x] {
		path[i] = y
		dfs(i-1, x/y, min(mi, y), max(mx, y))
	}
}