1. question: 组合总和IV(中等)
给你一个由 不同 整数组成的数组 nums ,和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。
题目数据保证答案符合 32 位整数范围。
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/combination-sum-iv
示例 1:
1 2 3 4 5 6 7 8 9 10 11 12
| 输入:nums = [1,2,3], target = 4 输出:7 解释: 所有可能的组合为: (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1) 请注意,顺序不同的序列被视作不同的组合。
|
示例 2:
1 2
| 输入:nums = [9], target = 3 输出:0
|
提示:
1 2 3 4
| 1 <= nums.length <= 200 1 <= nums[i] <= 1000 nums 中的所有元素 互不相同 1 <= target <= 1000
|
2. answers
这道题也是完全背包问题,但是不单单是组合问题了,而是排列问题。在124题中,已经指明了,对于排列问题,需要外层遍历背包容量,内层遍历物品即可。
代码如下所示:
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 33 34 35 36 37
| public class Solution_0125 {
public int combinationSum4(int[] nums, int target) {
int[] dp = new int[target + 1];
dp[0] = 1;
for (int i = 1; i < dp.length; i++) {
for (int j = 0; j < nums.length; j++) {
if(i < nums[j]) dp[i] = dp[i];
else dp[i] = dp[i] + dp[i - nums[j]]; } }
return dp[target]; }
public static void main(String[] args) { System.out.println();
int[] nums = {1,2,3}; int target = 4;
Solution_0125 s = new Solution_0125();
System.out.println(s.combinationSum4(nums, target)); } }
|
3. 备注
参考力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 (leetcode-cn.com),代码随想录 (programmercarl.com)。