累加和為 K 的子數組問題

• 2022 年 10 月 23 日
• 筆記
• leetcode, 動態規劃, 數據結構, 演算法, 演算法和數據結構

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

更多

演算法和數據結構筆記