題目網址：https://leetcode.cn/problems/combination-sum-iv/

題意：給一元素皆不同的array nums 和一整數 target, 返回總合為 target 的元素排列個數。

答案保證符合 32-bit 整數範圍（而非 32-bit 有號整數）

進階：如果 nums 中允許有負數, 需要向題目中添加哪些限制條件?

Solution 1：（TLE 無法通過）

想法：利用 DFS, 類似 39. Combination Sum

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        int res = 0;
        dfs(nums, target, res);
        return res;
    }

private:
    void dfs(const vector<int>& nums, int& target, int& res){
        if (target == 0) {
            res++;
            return;
        }

        for (const auto& num : nums) {
            if (num > target) {
                continue;
            }

            target -= num;
            dfs(nums, target, res);
            target += num;
        }
    }
};
  • time：$O(n \cdot 2^n)$ ➔ 最差情況應為 $O(n \cdot 2^n)$, 但是遞迴時會用 num > target 來進行剪枝(pruning), 所以實際運行情況是遠小於 $O(n \cdot 2^n)$ 的
  • space：$O(target)$ ➔ 取決於遞迴深度, 最大遞迴深度為 target

Solution 2：

想法：利用 DP, 來避免重複計算, 其中 dp[i] 表示 nums 中加總為 i 之排列數, e.g. 下圖中紅框部分 dp[2] 重複計算, 故用 dp 保存計算過的結果

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        vector<int> dp(target + 1, 0);
        dp[0] = 1; // 總和為 0, 也就是任何元素都不取, 方法數為 1

        for (int i = 1; i <= target; ++i) {
            for (const auto& num : nums) {
                if (i >= num) {
                    dp[i] += dp[i - num];
                }
            }
        }

        return dp.back();
    }
};
  • time：$O(target \cdot n)$ ➔ for loop, 其中 n 為 nums 的長度
  • space：$O(target)$ ➔ dp

進階問題

Q：如果 nums 中允許有負數, 需要向題目中添加哪些限制條件?

A：假設 nums 為 [a, -b] (其中 a > 0, b > 0), 且 target 為 0 ➔ a * (-b) + (-b) * a = 0
在該排列的後面添加 b 個 a 和 a 個 -b 後, 得到的新排列的元素之和仍然等於 target
➔ 如果允許負數出現, 則必須限制排列的最大長度, 避免出現無限長度的排列, 這樣才能計算排列數