377.组合总和4

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

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

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

回溯算法很好写代码，但是会超时

Solution

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
import java.util.Arrays;

class Solution {
    // 主方法，计算达到目标数 target 的所有可能的组合数
    public int combinationSum4(int[] nums, int target) {
        int[] memo = new int[target + 1]; // 初始化记忆化数组，大小为 target + 1
        Arrays.fill(memo, -1); // 将记忆化数组的所有元素初始化为 -1，表示未计算过
        return dfs(target, nums, memo); // 调用深度优先搜索方法
    }

    // 深度优先搜索方法
    private int dfs(int i, int[] nums, int[] memo) {
        if (i == 0) { // 基本条件：如果目标值 i 为 0，表示找到一种组合，返回 1
            return 1;
        }
        if (memo[i] != -1) { // 如果 memo[i] 已经计算过，直接返回缓存中的值
            return memo[i];
        }
        int res = 0; // 初始化结果变量 res
        for (int x : nums) { // 枚举所有可以选择的数
            if (x <= i) { // 如果当前数 x 小于或等于目标值 i
                res += dfs(i - x, nums, memo); // 递归计算目标值为 i - x 的组合数
            }
        }
        return memo[i] = res; // 将结果存储到 memo[i] 中，并返回结果
    }
}

dp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    // 主方法，计算达到目标数 target 的所有可能的组合数
    public int combinationSum4(int[] nums, int target) {
        // 初始化一维数组 f，大小为 target + 1
        int[] f = new int[target + 1];
        // 设置初始状态，目标为 0 的组合数为 1
        f[0] = 1;

        // 遍历每个目标值从 1 到 target
        for (int i = 1; i <= target; i++) {
            // 遍历数组 nums 中的每个数
            for (int x : nums) {
                // 如果当前数 x 小于或等于当前目标值 i
                if (x <= i) {
                    // 更新 f[i]，累加使用当前数 x 后的组合数
                    f[i] = f[i - x] + f[i];
                }
            }
        }

        // 返回目标值 target 的所有可能的组合数
        return f[target];
    }
}