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];
}
}
2016年7月25日星期一
[LeetCode] #377 Combination Sum IV
订阅:
博文评论 (Atom)
没有评论:
发表评论