累加和为 K 的子数组问题 _生活百科

累加和为 K 的子数组问题作者：Grey
原文地址：
【累加和为 K 的子数组问题】博客园：累加和为 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] * timesfor (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号位置开始及其后面的所有，帮我搞定targetpublic static List<List<Integer>> combinationSum(int[] arr, int k) {return p(arr, arr.length, 0, k);}// 从i号位置开始及其后面的所有，帮我搞定targetprivate 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;}}更多算法和数据结构笔记

累加和为 K 的子数组问题

推荐阅读

2022年西安社保补缴新规是怎样的？社保可以怎么补缴？

手机做泥游戏叫什么名字？做水晶泥游戏攻略[多图]

八字算命：1998年出生的人是什么命

华阴市算命最准的在哪

写自媒体文章从这3个方面入手自媒体文章该如何写？

带瑞字的女孩名字含义含有瑞字的女孩名字

石嘴山市惠农区宇泽副食商行_工商信用信息_经营范围期限状态_法人_地址_注册资本_怎么样

【健康知识】大闸蟹公蟹和母蟹的区别大闸蟹公的还是母的好吃!

维度强度极性程度是什么意思

清江鱼吃什么长大的清江鱼多大的好吃

电动牙刷和普通牙刷的区别区别在这里

十大富贵日柱有哪些

图木舒克哪里算命准

魅族18 pro防水吗

男孩带星字有寓意的名字

今年什么时候打春2020 今年什么时候打春2020几点几分

重庆巴南哪里可以摘樱桃 2021重庆巴南东温泉桃子采摘攻略

微信上看直播可不可以投影到电视上微信上看直播可不可以投影到电视

上班期间吵架发病算工伤吗？

环氧树脂水晶胶配方水晶胶去除方法介绍