小编点评

**累加和为 K 的子数组问题** **思路：** 动态规划 **算法：** 1. **base case：** * 如果数组长度为 0，则所有子数组都为空列表。 * 如果目标和为 0，则所有子数组都是空列表。 2. **普遍情况：** * 枚举每个位置的次数，并考虑每个位置收集的集合大小。 * 对于每个集合，检查其大小是否等于目标。 * 如果找到满足条件的集合，则将其加入结果列表中。 3. **递归处理：** * 对于每个位置，考虑收集的集合大小和目标和。 * 对于每个集合大小，枚举所有可能的组合。 * 对于每个组合，如果其大小等于目标，则将其加入结果列表中。 * 如果集合大小大于目标，则将其加入结果列表中，并考虑继续收集的集合。 **时间复杂度：**O(n * k)，其中 n 是数组长度，k 是目标和。 **空间复杂度：**O(n)，其中 n 是数组长度。 **示例：** **输入：** ``` arr = [1, 2, 3, 4, 5] k = 6 ``` **输出：** ``` [[1, 1, 1, 1, 1, 1]] ``` **解释：** 该程序通过枚举每个位置的集合大小来求所有满足条件的子数组。由于数组中所有元素都是正数，因此每个子数组的所有元素必须相同。

正文

累加和为 K 的子数组问题

作者：Grey

原文地址：

博客园：累加和为 K 的子数组问题

CSDN：累加和为 K 的子数组问题

题目说明

数组全为正数，且每个数各不相同，求累加和为K的子数组组合有哪些，

注：数组中同一个数字可以无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

题目链接见：LeetCode 39. Combination Sum

主要思路

使用动态规划来解，定义如下递归函数

List<List<Integer>> p(int[] arr, int len, int i, int k)

递归含义表示：数组从 i 开始，一直到最后，可以得到的子数组满足数组之和等于 k 的子数组组合有哪些。

首先是 base case

        if (i == len) {
            return new ArrayList<>();
        }
        List<List<Integer>> ans = new ArrayList<>();
        if (k == 0) {
            ans.add(new ArrayList<>());
            return ans;
        }

当 i 到数组结尾位置下一个位置，说明，i 到头了，不能继续往后找了，直接返回一个空列表，

当 k 等于 0，直接返回一个包含空列表的列表，表示一个数也没有，组合之和等于 0。

接下来是普遍情况，枚举每个位置有 times 个的情况下，往后收集的集合数是多少，即

for (int times = 0; times * arr[i] <= k; times++) {
    // 每个位置有 times 的情况下，往后收集的集合个数           
}

由于数组中全是正数，所以前提是: times * arr[i] <= k，

如果times * arr[i]正好等于 k，说明收集到了一个满足条件的集合，这个集合里面有 times 个 arr[i]，

for (int times = 0; times * arr[i] <= k; times++) {
    // 每个位置有 times 的情况下，往后收集的集合个数
    if (times * arr[i] == k) {
        List<Integer> t = new ArrayList<>();
        // 收集到了一种情况，即集合里面有 times 个 arr[i]
        for (int j = 0; j < times; j++) {
                t.add(arr[i]);
        }
        ans.add(t);
        return ans;
    }
    ……           
}

接下来就是当前位置 i 搞定 times * arr[i]，i + 1 以后的数组搞定k - times * arr[i]，

        for (int times = 0; times * arr[i] <= k; times++) {
            if (times * arr[i] == k) {
                List<Integer> t = new ArrayList<>();
                for (int j = 0; j < times; j++) {
                    t.add(arr[i]);
                }
                ans.add(t);
                return ans;
            }
            // 剩下的位置搞定 k - arr[i] * times
            for (List<Integer> a : p(arr, len, i + 1, k - times * arr[i])) {
                for (int j = 0; j < times; j++) {
                    a.add(arr[i]);
                }
                ans.add(a);
            }
        }
        return ans;

完整代码如下

class Solution {

    // 从i号位置开始及其后面的所有，帮我搞定target
    public static List<List<Integer>> combinationSum(int[] arr, int k) {
        return p(arr, arr.length, 0, k);
    }

    // 从i号位置开始及其后面的所有，帮我搞定target
    private static List<List<Integer>> p(int[] arr, int len, int i, int k) {

        if (i == len) {
            return new ArrayList<>();
        }
        List<List<Integer>> ans = new ArrayList<>();
        if (k == 0) {
            ans.add(new ArrayList<>());
            return ans;
        }

        for (int times = 0; times * arr[i] <= k; times++) {
            if (times * arr[i] == k) {
                List<Integer> t = new ArrayList<>();
                for (int j = 0; j < times; j++) {
                    t.add(arr[i]);
                }
                ans.add(t);
                return ans;
            }
            for (List<Integer> a : p(arr, len, i + 1, k - times * arr[i])) {
                for (int j = 0; j < times; j++) {
                    a.add(arr[i]);
                }
                ans.add(a);
            }
        }
        return ans;
    }
}

更多

算法和数据结构笔记