Leetcode--Java--377. 组合总和 Ⅳ

题目描述

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

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

样例描述

示例 1：

输入：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：

输入：nums = [9], target = 3
输出：0

思路

动态规划
状态表示和状态计算如下： 时间复杂度为0(target n),target为状态数量，每个状态要划分为n个子集。

1. 考虑最后一个数aj（图中以一段坐标表示一个数）的不同的取法，对应不同的划分方案。每个划分方案都是以aj数作为结尾，因此aj左边的划分方案数累加起来就是整个的划分方案。这里枚举不断最后一个数，直到target即可
2. 转移的条件要注意状态值i一定要大于划分出的数num[j]。
3. 初始如果0的话只有一种拆分方案，就是空集。
4. **进阶：**如果包含负数的话，状态之间转移会存在环，就不能用dp，因为状态之间会有依赖关系，方案数可能有无穷多种，如下1和-1凑2的话，可能为1 - 1, 1 - 1 + 1 - 1… （没法做了
   
5. 不要直接思维定势用背包问题，这个不等同于背包问题

代码

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