1. 首頁 > 生活百科 > >

累加和為 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;}}更多算法和數據結構筆記

    推薦閱讀