首页 > 代码库 > Combination Sum IV -- LeetCode
Combination Sum IV -- LeetCode
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 = 4The 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?
思路：递归求解。
为了避免相同的解重复计数，要将原数组中的重复数字剔除，这样子所有的情况都只会枚举一遍。
同时，为了提速，在递归过程中，可以用一个map记录子问题的结果，这样就可以节省时间。
补充：如果数组中有负数，则应该添加的额外条件是最多可以有几个数相加。
1 class Solution { 2 public: 3 int help(vector<int>& nums, int target, unordered_map<int, int>& solutionCount) { 4 int count = 0; 5 for (int i = 0; i < nums.size() && nums[i] <= target; i++) { 6 if (nums[i] < target) { 7 int balance = target - nums[i]; 8 if (solutionCount.count(balance)) 9 count += solutionCount[balance];10 else {11 int subCount = help(nums, balance, solutionCount);12 solutionCount.insert(make_pair(balance, subCount));13 count += subCount;14 }15 }16 else count++;17 }18 return count;19 }20 int combinationSum4(vector<int>& nums, int target) {21 if (nums.size() == 0) return 0;22 sort(nums.begin(), nums.end(), less<int>());23 vector<int> distinctNum(1, nums[0]);24 unordered_map<int, int> solutionCount;25 for (int i = 1; i < nums.size(); i++)26 if (nums[i] != nums[i-1]) distinctNum.push_back(nums[i]);27 return help(distinctNum, target, solutionCount);28 }29 };
Combination Sum IV -- LeetCode
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。