【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时会超时
    }
}