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

推荐阅读

不倒翁小鸟的制作教程

山药圆子怎么做才好吃，肉末山药圆子的做法？

熟黄芪泡水喝的功效与作用熟黄芪泡水喝有哪些功效与作用

饭圈拉瓜是什么意思饭圈拉郎是什么意思

父母买房可以写未成年孩子的名字吗,规避转让税但不能贷款

关于特别认真地生活简述特别认真地生活

办银行卡需要什么办银行卡需要什么证件和材料

关于淮北公交简述淮北公交

大红袍分几种肉桂

孕妇铅过高有什么症状有什么不良影响

终不似少年游终不似少年游

柠檬片的功能与功效柠檬片的功效作用

防弹咖啡怎么做好喝防弹咖啡怎么做

excel查找不出来是什么原因

今年广东调整养老金的新消息 2022广东省养老金上调方案及补发时间

毓字取名女孩有寓意属兔最搭的名字有哪些？

强势老人是家庭的灾难【老人强势发生家庭矛盾】

昆明机场离哪个高铁站近，昆明飞机场到高铁站有多远？

“魑魅魍魉” 你们知道怎么读吗？魑魅魍魉怎么读

糖尿病人适合送的礼品女总裁给男秘书送粥