累加和为 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;

    }

}

算法和数据结构笔记