Formatted question description: https://leetcode.ca/all/377.html
/** 377. Combination Sum IV 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? */
One-dimensional array dp, where
dp[i] represents the number of solutions whose target number is i, and then traverses from 1 to target.
For each number i, traverse the nums array, if i>=x
int dp = new int[target + 1];
If there is negative numbers allowed, there could be infinite possibilities.
- e.g. target = 1, there is
[-1, 1]in nums, then the possible ways could be
If allowing negative numbers, there can’t be any
combiantion of neigatie numers +
any combiantion of positive numbers == 0.