LeetCode-377. 组合总和 Ⅳ

蔚落 2024-03-25 16:51 7阅读 0赞

题目来源  
[377. 组合总和 Ⅳ][377. _]

### 题目分析 ###

本题题目描述说是求组合，但又说是可以元素相同顺序不同的组合算两个组合，其实就是求排列！  
可以做下[518.零钱兑换II][518._II]，这道题是排列，零钱兑换II是组合  
再多说一句:组合和排列一个是先遍历物品，再遍历重量，另一个是先遍历重量，在遍历物品

### 回溯法 ###

class Solution {
        
        int ans = 0;
        public int combinationSum4(int[] nums, int target) {
        
            if(nums == null || nums.length < 1){
        
                return 0;
            }
            backTracking(nums,target,0);
            return ans;
        }
    
        private void backTracking(int[] nums,int target,int sum){
        
            if(sum == target){
        
                ans++;
            }
            if(sum > target){
        
                return;
            }
            for(int i = 0;i<nums.length;i++){
        
                sum += nums[i];
                backTracking(nums,target,sum);
                sum -= nums[i];
            }
        }
    }

![在这里插入图片描述][b4c4368a71b84151a3493ac7a0c30560.png]

### 动态规划(压缩) ###

*  1.确定dp数组以及下标的含义

dp\[i\]: 凑成目标正整数为i的排列个数为dp\[i\]

*  2.确定递推公式

dp\[i\]（考虑nums\[j\]）可以由 dp\[i - nums\[j\]\]（不考虑nums\[j\]） 推导出来。  
求装满背包有几种方法，递推公式一般都是dp\[i\] += dp\[i - nums\[j\]\];

*  3.dp数组如何初始化

因为递推公式dp\[i\] += dp\[i - nums\[j\]\]的缘故，dp\[0\]要初始化为1，这样递归其他dp\[i\]的时候才会有数值基础。

*  4.确定遍历顺序

如果求组合数就是外层for循环遍历物品，内层for遍历背包。  
如果求排列数就是外层for遍历背包，内层for循环遍历物品。

*  5.举例来推导dp数组

nums = \[1,2,3\], target = 4  
![在这里插入图片描述][3084ed88b2a644f4a42c0a76588264f3.png]  
整体代码

class Solution {
        
        public int combinationSum4(int[] nums, int target) {
        
            if(nums == null || nums.length < 1){
        
                return 0;
            }
            int[] dp = new int[target+1];
            dp[0] = 1;
            for(int i = 0;i<=target;i++){
        
                for(int j = 0;j<nums.length;j++){
        
                    if (i >= nums[j]) {
        
                        dp[i] = dp[i] + dp[i - nums[j]];
                    }
                }
            }
            return dp[target];
        }
    }

![在这里插入图片描述][7dd21af5988c4d7181d31aaf2ee93a25.png]

[377. _]: https://leetcode.cn/problems/combination-sum-iv/
[518._II]: https://donglin.blog.csdn.net/article/details/129580937
[b4c4368a71b84151a3493ac7a0c30560.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/bec77fbc77e14d09aa1a48ab4aa9f494.png
[3084ed88b2a644f4a42c0a76588264f3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/30987a22618440d7a614a68f66cc8b21.png
[7dd21af5988c4d7181d31aaf2ee93a25.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/45a34a3998714245ac7b2c3e607ea0e5.png