377. Combination Sum IV - Medium

前往題目

想法

• 會不會是用backtracking?

思路

1. 利用array當作cache
2. base case是0，因為只有一種組合是0
3. 接著疊代1~target，逐步建立cache
4. 每個循環裡面要再看一次所有的nums並相加，因為先前的加起來才是當前的組合總數

可以看這個discussion的解釋，非常清楚

Code

class Solution {
    public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target + 1];

        // 1 way to form 0
        dp[0] = 1;

        // 1 ~ target
        for (int i = 1; i <= target; ++i) {
            // Add up previous combinations
            for (int num : nums) {
                if (i - num >= 0) {
                    dp[i] += dp[i - num];
                }
            }
        }

        return dp[target];
    }
}