Description: Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.
Example:
nums = [1, 2, 3] target = 4 The possible combination ways are: (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1) Note that different sequences are counted as different combinations. Therefore the output is 7.Follow up: What if negative numbers are allowed in the given array? How does it change the problem? What limitation we need to add to the question to allow negative numbers?
问题描述: 给定整数数组,其元素为整数且没有重复元素，找出可能的和为target(注意，不同的序列被认为是不同的组合)的组合的个数
问题分析: 三种解法: naive dfs(TLE) naive dfs + memorization dp
解法1(dfs + memorization):
class Solution { int[] dp; public int combinationSum4(int[] nums, int target) { dp = new int[target + 1]; Arrays.fill(dp,-1); dp[0] = 1; return recursive(nums,target); } public int recursive(int[] nums,int target){ if(dp[target] != -1) return dp[target]; int sum = 0; for(int i = 0;i < nums.length;i++){ if(target >= nums[i]) sum += recursive(nums,target - nums[i]); } dp[target] = sum; return sum; } }解法2(dp):
class Solution { public int combinationSum4(int[] nums, int target) { int[] comb = new int[target + 1]; comb[0] = 1; for(int i = 1; i < comb.length; i++){ for(int j = 0; j < nums.length; j++){ if(i - nums[j] >= 0){ comb[i] += comb[i - nums[j]]; } } } return comb[target]; } }