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

累加和为 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] * 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 的子数组问题】

累加和为 K 的子数组问题

经验总结扩展阅读

微信限额20万是一年吗

4天后，不断回首，品味离别痛，一直怀念，等爱来，与旧爱赴余生

五伏天是什么意思三伏天为什么要吃鸭

吃清江鱼的好处和坏处吃清江鱼对人有什么好处和坏处呢

|73岁老人直播教成年人识字：他们不该被忽视

蜥蜴长什么样?

翡翠镯子有斜裂纹怎么办

脾虚能引起失眠吗调理手段让你摆脱烦恼

颐和园的基本现状介绍

儿童房需要装壁灯吗宜家儿童壁灯怎么安装

选购的油烟机时候要注意哪些?

力言的寓意是什么？

原神暂留此影任务怎么过

冰雪聪明是什么意思啊冰雪聪明的意思

浪漫的爱情弟弟现在又没钱，你们不出彩礼钱，那谁来出？

达人分享养狗必知的常识柯基犬换毛期三大护理技巧

一如|人间四月，有情可寄

恋爱过程与结果，你更在意哪一个？

昆山女子整容后山根晃动、鼻尖发白！手术方：很成功，已起诉

proton是什么车？