算法题每日一练：组合总和 Ⅳ

一、问题描述

给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。

题目数据保证答案符合 32 位整数范围。

题目链接：组合总和 Ⅳ

二、题目要求

样例

输入： 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)请注意，顺序不同的序列被视作不同的组合。

考察

1.动态规划2.建议用时20~35min

三、问题分析

这一题和我们之前刷的算法题每日一练---第87天：组合总和几乎是一模一样，但是数据的范围变大了好多（元素个数从 30 变到 200，递归的深度变得太深了，没法解决），所以当我用同样的方法时超时了。

看了题解才发现这一题原来要用递归算法，所以今天我们的回溯算法四式打不了了，但可以试试我之前讲解的动态规划三步走战略。

第一步：含义搞懂

通常动态规划都会用数组 dp[]存放东西，那存放在数组里面的究竟是什么？

这要看题目问我们什么，这一题就问告诉我们 target 的值，求解所有可能的组合总数。那么我们就定义 dp[i]代表总和为 i 的组合总数。

第二步：变量初始

初始化数据直接dp[0]=1 就行了，因为当 target 等于 0 的时候，只有一种组合总数。

第三步：关系归纳

这一题如何找出数之间的关系呢？

上面的树状图再抽象一下。

是不是能发现一点规律了，如果有效组合的末尾为 1，那么我们把末尾的 1 去掉，只需要在数组[1,2,3]求出 4-1=3 即 dp[3]的总组合个数。

此时的末尾数字如果还是 1，那么我们再把末尾的 1 去掉,只需要在数组[1,2,3]求出 3-1=2 ,即 dp[2]的总组合个数。

......

所以，最终的规律为dp[i]+=dp[i-nums[j]]。

三步走，打完收工！

四、编码实现

class Solution {public:    int combinationSum4(vector<int>& nums, int target) {        vector<unsigned long long>dp(target+1);//初始化        int i,j;        dp[0]=1;        for(i=1;i<=target;i++)        {            for(j=0;j<nums.size();j++)            {                if(i>=nums[j])                {                    dp[i]+=dp[i-nums[j]];//关系归纳                }            }        }        return dp[target];//输出结果    }};

数组定义成无符号 unsigned long long 为了避免测试样例中的溢出。

五、测试结果