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?
A:
仔细读题啊, 一开始理解错了。
*************** DP with memorization ************
class Solution { public: int combinationSum4(vector<int>& nums, int target) { sort(nums.begin(), nums.end()); unordered_map<int, int> map; return helper(nums, target, map); } private: int helper(vector<int> & nums, int target, unordered_map<int,int> & map){ if( target<0){ return 0; } if(target == 0 ){ return 1; } auto iter = map.find(target); if(iter != map.end()) return iter->second; int res = 0; for(int i = 0;i<nums.size(); i++){ res += helper(nums, target - nums[i], map); } map[target] = res; return res; } };
No comments:
Post a Comment