LintCode 564 · Combination Sum IV.java

Backpack with Value array:
note that: "A number in the array can be used multiple times in the combination."
function:
dp[i] += dp[i - nums[j - 1]]; (when you take that ith item)
or
dp[i] = 0; (when you don't take that ith item)

	public class Solution {
	/**
	* @param nums: an integer array and all positive numbers, no duplicates
	* @param target: An integer
	* @return: An integer
	*/
	public int backPackVI(int[] nums, int target) {
	// write your code here
	if (nums == null || nums.length == 0) {
	return 0;
	}
	int n = nums.length;
	int[] dp = new int[target + 1];
	// dp: init
	dp[0] = 1;
	// dp: states + functions
	for (int i = 1; i <= target; i++) {
	for (int j = 1; j <= n; j++) {
	if (i >= nums[j - 1]) {
	dp[i] += dp[i - nums[j - 1]];
	}
	}
	}
	// dp: answer
	return dp[target];
	}
	}

view raw 564 · Combination Sum IV.java hosted with ❤ by GitHub