Question
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?
*/
Algorithm
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];
Follow up
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-1+1+1
,-1-1+1+1+1
…
If allowing negative numbers, there can’t be any combiantion of neigatie numers
+ any combiantion of positive numbers
== 0.
Code
Java
-
public class Combination_Sum_IV { class Solution { public int combinationSum4(int[] nums, int target) { // dp[i] meaning for value i, how many combination count int[] dp = new int[target + 1]; dp[0] = 1; for (int targetValue = 1; targetValue <= target; targetValue++) { for (int i = 0; i < nums.length; i++) { if (nums[i] <= targetValue) { // @note: not dp[targetValue]=dp[targetValue-a]+dp[a] // becasue both will be added in below line for dp[a] and dp[targetValue-a] dp[targetValue] += dp[targetValue - nums[i]]; } } } return dp[target]; } } }
-
// OJ: https://leetcode.com/problems/combination-sum-iv/ // Time: O(NT) // Space: O(T) class Solution { unordered_map<int, int> m { {0, 1} }; int dp(vector<int>& nums, int target) { if (m.count(target)) return m[target]; int cnt = 0; for (int n : nums) { if (n > target) break; cnt += dp(nums, target - n); } return m[target] = cnt; } public: int combinationSum4(vector<int>& nums, int target) { sort(nums.begin(), nums.end()); return dp(nums, target); } };
-
class Solution(object): def combinationSum4(self, nums, target): """ :type nums: List[int] :type target: int :rtype: int """ dp = [0] * (target + 1) dp[0] = 1 for i in range(1, target + 1): for j in range(1, len(nums) + 1): if i - nums[j - 1] >= 0: dp[i] += dp[i - nums[j - 1]] return dp[-1]