题目描述：
给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。
题目数据保证答案符合 32 位整数范围。
数据范围：
$1\le nums.len \le 200; 1\le nums[i] \le 1000; 1\le target \le 1000$
题解：
同一元素可以无限制选取，但是有顺序区分。如果没有顺序区分的话就是简单的组合问题，完全背包就能解决。
1
2
3
4
5
6
| dp[0] = 1;
for(int i = 0; i < n; ++i)
{
for(int j = nums[i]; j <= target; ++j)
dp[j] += dp[j - nums[i]];
}
|
但是有顺序区分，是一个排列，可以枚举排列的最后一个数字。
先枚举背包容量，再枚举最后一位。这样的话 $nums[i]$ 前面也可以有 $nums[j], j > i$ 。
组合的方式只能使得 $nums[i]$ 的前面只有 $nums[j], j < i$ 。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const int INF = 0x3f3f3f3f;
int combinationSum4(vector<int> &nums, int target)
{
int n = nums.size();
vector<int> dp(target + 1, 0);
dp[0] = 1;
for (int i = 1; i <= target; ++i)
{
for (auto &x : nums)
{
if (x <= i && dp[i - x] < INT_MAX - dp[i])
{
dp[i] += dp[i - x];
}
}
}
return dp[target];
}
};
|