377. Combination Sum IV

一刷 06/2022

Version #1 DP

一开始写不出来是错在每一层加0到n number of nums[i]

应该是每一层选一个nums[i]加入就可以了

Time O(Target * N) -> N is #numbers

Space O(Target)

Runtime: 2 ms, faster than 59.29% of Java online submissions for Combination Sum IV.

Memory Usage: 41.6 MB, less than 43.21% of Java online submissions for Combination Sum IV.

class Solution {

    public int combinationSum4(int[] nums, int target) {

        int[] count = new int[target + 1];

        count[0] = 1;

        for (int sum = 1; sum <= target; sum++) {

            for (int num : nums) {

                if (sum - num >= 0) {

                    count[sum] += count[sum - num];

                }

            }

        }

        return count[target];

    }

}