【LeeCode】377. 组合总和 Ⅳ

【题目描述】

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

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

​​https://leetcode.cn/problems/combination-sum-iv/​​

【示例】

【代码】

这里还是老老实实采用 【动态规划】

package com.company;
// 2023-1-6
import java.util.*;

class Solution {
    public int combinationSum4(int[] nums, int target) {
        // dp[i] 和为i在nums中出现过的元素有dp[i]个
        int[] dp = new int[target + 1];
        // 初始值: dp[0] 和为0的只有0这1个元素
        dp[0] = 1;

        // 完全背包: 组合(有顺序要求)  外层: target  内层: nums
        for (int i = 1; i <= target; i++) {
            for (int num: nums) {
                if (i >= num){
                    dp[i] = dp[i] + dp[i - num];
                }
            }
        }
        System.out.println(Arrays.toString(dp));
        return dp[target];
    }
}
public class Test {
    public static void main(String[] args) {
        new Solution().combinationSum4(new int[]{1, 2, 3}, 4);   // 输出: 7
        new Solution().combinationSum4(new int[]{9}, 3);      // 输出: 0
    }
}

【代码】admin

通过率  8 / 15  这里采用【dfs的回溯 + 剪枝】算法，可以处理简单的计算，如果target太大会超时()

package com.company;
// 2023-1-6
import java.util.*;

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    LinkedList<Integer> list = new LinkedList<>();
    public int combinationSum4(int[] nums, int target) {
        if (nums.length == 0 || target < 0) return -1;
        // 很关键的一步,因为每次都是从第一个值开始累积,如果第一个值过大导致后面的计算直接跳过了
        Arrays.sort(nums);
        dfs(nums, target, 0, 0, list);
        System.out.println(res);
        return res.size();
    }

    private void dfs(int[] nums, int target, int index,  int sum, LinkedList<Integer> list) {
        if (sum == target){
            res.add(new LinkedList<>(list));
            return;
        }

        for (int i = index; i < nums.length && sum + nums[i] <= target; i++){
            sum += nums[i];
            list.add(nums[i]);
            dfs(nums, target,0, sum, list);
            sum -= nums[i];
            list.removeLast();
        }
    }
}
public class Test {
    public static void main(String[] args) {
        new Solution().combinationSum4(new int[]{1, 2, 3}, 4);   // 输出: 7
        new Solution().combinationSum4(new int[]{9}, 3);         // 输出: 0
        new Solution().combinationSum4(new int[]{3,1,2,4}, 4);   // 输出: 0
        new Solution().combinationSum4(new int[]{4, 2, 1}, 4);   // target = 32时会超时
    }
}