Leet code (Medium) : 377. Combination Sum IV - JAVA

 

class Solution {
    public int combinationSum4(int[] nums, int target) {
        // 인덱스 숫자가 되기 위한 구성 갯수를 저장하는 배열 
        int[] sumCount = new int[target+1]; // 선언만으로 모두 0으로 채워짐.
        sumCount[0] = 1;

        for(int sum = 1; sum <= target; sum++){
            for(int i = 0; i < nums.length; i++){
                if(nums[i] <= sum){ // 요소가 target보다 작으면 구성요소가 될수 있음
                    // nums[i]를 포함해서 구성하는 수를 각각 더하기
                    // nums[i]는 무조건 포함할테니 고정하고 sum-nums[i]의 구성수를 더하면 됨.
                    sumCount[sum] += sumCount[sum - nums[i]];
                }
            }
        }

        return sumCount[target];
    }
}