给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。

示例:

nums = [1, 2, 3]
target = 4

所有可能的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)

请注意，顺序不同的序列被视作不同的组合。

因此输出为 7。

 

思路：

本题相等于每个数可以用无数次  要找到指定的和为target的种类数  即每次重新从数组中找到和为target-nums[i]的种类数  

1.先写递归----会超时，再改写动态规划

// 先写递归
	public int combinationSum4(int[] nums, int target) {
		if (target == 0) {
			return 1;
		}
		int res = 0;
		for (int i = 0; i < nums.length; i++) {
			if (target >= nums[i]) {
				// 递归去找target-nums[i]
				res += combinationSum4(nums, target - nums[i]);
			}
		}
		return res;
	}

2.动态规划

    // 动态规划
	public int combinationSum(int[] nums, int target) {
	    int[] dp = new int[target + 1];
		dp[0] = 1; // 和为0的情况
		for (int i = 1; i <= target; i++) {  //列出所有和为target的情况
			int temp = 0;
			for (int j = 0; j < nums.length; j++) {  //每次都可以用整个数组的元素
				if (i >= nums[j]) {
					temp += dp[i - nums[j]];
				}
			}
			dp[i] = temp;
		}
		return dp[target];
	}