[LeetCode] 每日一题 368. 最大整除子集（dfs + 记忆化搜索）

题目链接

https://leetcode.cn/problems/largest-divisible-subset

题目描述

给你一个由 无重复 正整数组成的集合 nums ，请你找出并返回其中最大的整除子集 answer ，子集中每一元素对 (answer[i], answer[j]) 都应当满足：

• answer[i] % answer[j] == 0 ，或

• answer[j] % answer[i] == 0

如果存在多个有效解子集，返回其中任何一个均可。

示例输入

示例 1

输入：nums = [1,2,3]
输出：[1,2]
解释：[1,3] 也会被视为正确答案。

示例 2

输入：nums = [1,2,4,8]
输出：[1,2,4,8]

提示

• 1 <= nums.length <= 1000

• 1 <= nums[i] <= 2 * 10^9

• nums 中的所有整数 互不相同

解题思路

这道题属于典型的子序列问题，只不过子序列的判定条件不是大小关系，而是整除关系，要求返回一个最大整除子集

我的第一想法是用DFS + 记忆化搜索来做，这种方式不仅能高效求出每个元素作为结尾时的最长整除链，还能借助 pre[] 数组记录每一步的选择，从而在最后一步还原整除子集

具体思路如下：

1. 先对数组进行排序，这样能保证对于任意一对 nums[i] % nums[j] == 0 的合法情况，有 i > j

2. 定义 dfs(i) 表示以 nums[i] 为结尾的最大整除子集长度

3. 使用 memory[] 做记忆化，避免重复计算

4. 使用 pre[] 数组记录每个位置上整除子集链的前一个元素

5. 在主循环中尝试以每个元素作为结尾，记录最长链的长度和下标

6. 最后根据 pre[] 倒序回溯出最终的整除子集

这种写法其实有点类似我们在背包问题里使用递推加路径记录，还挺有意思的 😊

class Solution {
    List<Integer> ans = new ArrayList<>();

    public List<Integer> largestDivisibleSubset(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        int[] memory = new int[n];
        int[] pre = new int[n];
        Arrays.fill(pre, -1);
        int maxLen = 0;
        int maxIndex = 0;
        for (int i = 0; i < n; i++) {
            int len = dfs(i, nums, memory, pre);
            if (len > maxLen) {
                maxIndex = i;
                maxLen = len;
            }
        }
        List<Integer> ans = new ArrayList<>(maxLen);
        for (int i = maxIndex; i >= 0; i = pre[i]) {
            ans.add(nums[i]);
        }
        return ans;
    }

    private int dfs(int index, int[] nums, int[] memory, int[] pre) {
        if (memory[index] != 0) {
            return memory[index];
        }
        int temp = 0;
        for (int i = 0; i < index; i++) {
            if (nums[index] % nums[i] != 0) {
                continue;
            }
            int len = dfs(i, nums, memory, pre);
            if (len > temp) {
                temp = len;
                pre[index] = i;
            }
        }
        memory[index] = temp + 1;
        return temp + 1;
    }
}

复杂度分析

• 时间复杂度：O(n^2)，每个元素都可能和之前所有元素做整除判断 🚀

• 空间复杂度：O(n)，主要用于记忆化数组 memory[] 和路径追踪数组 pre[] 💾

总结

这道题的核心在于构造“整除链”，我选择用 DFS + 记忆化来构建这条链的最大长度，并借助 pre[] 实现路径回溯，代码结构清晰，效率也不错。相比动态规划的递推写法，这种“递归 + 回溯”的方式更贴合我的直觉思路，也更加易于维护与调试 👍

希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。