2016年7月25日星期一

[LeetCode] #377 Combination Sum IV


public class Solution {
    // state[i]: how many combinations when target = i
    // state[i] += 1, when num == i
    //             state[i - num], num=nums[0], ..., nums[nums.length - 1]
    // result = state[target];
    public int combinationSum4(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        Arrays.sort(nums);
        int state[] = new int[target + 1];
        state[0] = 0;
        for (int i = 1; i <= target; i++) {
            for (int num : nums) {
                if (num == i) {
                    state[i]++;
                } else if (num < i) {
                    state[i] += state[i - num];
                } else {
                    break;
                }
            }
        }
        return state[target];
    }
}


没有评论:

发表评论