题目描述

给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。

题目数据保证答案符合 32 位整数范围。

样例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 中的所有整数 互不相同

算法1

(动态规划 + 反推方案) $\mathcal O(n^2)$

• 整除具有传递性：如果整数a是某个整除子集中最大数b的倍数，那么a可以加入这个整除子集中获取一个更大的整除子集

• 由于当a < b时，a % b = a，所以我们可以将数组从小到大排序，然后转换成一个类似LIS的问题，其中上升的概念可以被定义为具有整除关系，即nums[j] % nums[i] = 0且j > i

• 状态表示：f[i]表示以nums[i]结尾的最大整除子集的长度，最大长度为max(f[0], ..., f[n-1])

• 状态转移：对于任意一个小于nums[i]的数nums[j]，满足nums[i] % nums[j] == 0，有f[i] = max(f[i], f[j] + 1)

• 初始化：对于任意的i，nums[i]都能单独构成一个整除子集，f[i] = 1

• 反推方案：记录最大整除子集的长度，每次遍历数组中所有下标找到对应f[i]使得f[i] == ans，然后将ans减一继续寻找前一个转移过来的值，直到ans = 1为止

• 前置知识：LeetCode300.最长上升子序列

Java 代码

class Solution {
    public List<Integer> largestDivisibleSubset(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        // 以nums[i]结尾的最大整除子集
        int[] f = new int[n];
        int ans = 1;
        for(int i = 0; i < n; i++){
            f[i] = 1;
            for(int j = 0; j < i; j++){
                if(nums[i] % nums[j] == 0){
                    f[i] = Math.max(f[i], f[j] + 1);
                }
            }
            ans = Math.max(ans, f[i]);
        }
        List<Integer> res = new ArrayList<>();
        int prev = -1;
        for(int i = ans; i >= 1; i--){
            for(int j = 0; j < n; j++){
                if(f[j] == i && (prev == -1 || prev % nums[j] == 0)){
                    res.add(nums[j]);
                    prev = nums[j];
                }
            }
        }
        return res;
    }
}