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

更多

算法和数据结构笔记

标签：