LeetCode Combination Sum IV

LeetCode 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?


给定一个数组,问从数组中有放回的取若干个数字,加起来等于target的方案数有多少种。

一开始以为是和LeetCode Combination Sum是类似的,只不过数字可以重复取而已,于是快速写出了如下的DFS版本:

class Solution {
private:
	void dfs(vector<int>& nums, int sum, int& ans) {
		if (sum == 0) {
			++ans;
			return;
		}
		if (sum < 0)return;
		for (const auto &i : nums) {
			if (sum >= i) {
				dfs(nums, sum - i, ans);
			}
		}
	}
public:
	int combinationSum4(vector<int>& nums, int target) {
		int ans = 0;
		dfs(nums, target, ans);
		return ans;
	}
};

悲剧的是TLE了,给了一个样例[1,2,3],target=32,结果有181997601种之多,DFS确实吃不消。

究其原因还是因为每个数可以重复取值,如果每个数最多取一次,也就相当于0/1背包,每个数可以取或者不取,则用DP很好办:

class Solution {
public:
	int combinationSum4(vector<int>& nums, int target) {
		vector<int> dp(target + 1, 0);
		dp[0] = 1;
		for (int i = 0; i < nums.size(); ++i) { // 对每个数字
			for (int j = target; j >= nums[i]; --j) {
				dp[j] += dp[j - nums[i]]; // 取值;不取dp[j]保持不变;所以取和不取加起来就是+=dp[j-nums[i]]
			}
		}
		return dp[target];
	}
};

但是这题中,每个数是可以重复取值的。因为数组中的数最小是1,所以每个数最多可以取target次,所以我们可以把0/1背包改成最多取target次的背包问题,也就是对于每个商品,我们可以尝试取1次、2次...target次。

我们可以换一种思路,假设dp[i-1]表示生成和为i-1的所有组合数,那么生成和为i的所有组合数等于所有生成和为i-nums[j]的组合数的和,即所有dp[i-nums[j]]的和。dp[i-nums[j]]表示减去nums[j]此时的组合数。

代码如下:

class Solution {
public:
	int combinationSum4(vector<int>& nums, int target) {
		vector<int> dp(target + 1, 0);
		dp[0] = 1;
		for (int i = 1; i <= target; ++i) {
			for (int j = 0; j < nums.size(); ++j) {
				if (i >= nums[j])dp[i] += dp[i - nums[j]];
			}
		}
		return dp[target];
	}
};

本代码提交AC,用时3MS。仔细观察这个版本的代码和上个版本的代码,发现其实就是两层循环换了一下位置,前者求不放回的方案数,后者求放回的方案数。

如果有负数,则要限制每个数的使用次数了,因为如果有数1和-1,要生成和为0的组合数,则可以有无限种,比如[1,-1],[1,1,-1,-1]。

Leave a Reply

Your email address will not be published. Required fields are marked *