LeetCode 377. 组合总和 Ⅳ Java 实现题目分析给定一个由不同正整数组成的数组 nums 和一个目标整数 target求有多少种不同的组合方式使得和为 target。顺序不同的组合视为不同即求排列数。例如 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)这是一个完全背包求排列数的问题。核心 DP 定义· dp[i] 表示凑成和为 i 的排列数。· 初始化 dp[0] 1凑成 0 有一种方式什么都不选。· 状态转移对于每个容量 i尝试所有数字 num 作为最后一个数字则剩余 i - num 有 dp[i - num] 种方式累加即可。关键点外层循环遍历容量 i内层循环遍历数字 num这样会考虑数字的顺序得到排列数。如果反过来外层物品内层容量则得到的是组合数。Java 实现classSolution{publicintcombinationSum4(int[]nums,inttarget){// dp[i] 表示凑成和为 i 的排列数int[]dpnewint[target1];dp[0]1;// 凑成 0 有一种方式空组合// 外层遍历容量内层遍历物品 - 求排列数for(inti1;itarget;i){for(intnum:nums){if(inum){dp[i]dp[i-num];}}}returndp[target];}}代码详解· dp[0] 1空序列和为 0视为一种方式。· 外层 i 从 1 到 target逐步计算每个和值的排列数。· 内层 num 遍历 nums尝试将 num 作为当前和 i 的最后一个元素。· 如果 i num说明可以用 num那么剩余部分 i - num 有 dp[i - num] 种排列方式。· 将所有可能累加得到 dp[i]。· 最终返回 dp[target]。样例追踪以 nums [1, 2, 3], target 4 为例i 计算过程 dp[i]0 初始 11 dp[0] (num1) 12 dp[1] (num1) dp[0] (num2) 1 1 23 dp[2] (num1) dp[1] (num2) dp[0] (num3) 2 1 1 44 dp[3] (num1) dp[2] (num2) dp[1] (num3) 4 2 1 7结果7复杂度分析· 时间复杂度O(target × n)其中 n 为 nums 的长度。双重循环外层 target内层 n。· 空间复杂度O(target)使用一维 DP 数组。扩展排列数 vs 组合数· 排列数本题外层遍历容量内层遍历物品。顺序不同算不同。· 组合数顺序无关外层遍历物品内层遍历容量正序因为是完全背包。例如 LeetCode 518. 零钱兑换 II。如果面试官追问为什么可以解释外层容量时每个 i 都会尝试所有可能的最后一个数字从而区分了顺序而外层物品时物品的使用顺序被固定不会重复计算不同顺序。注意事项· 题目保证结果可以用 32 位整数表示因此使用 int 即可。· nums 中的元素互不相同且为正整数无需考虑 0 或重复元素。· 如果 target 为 0根据题目约束 target 1但代码中 dp[0] 1 也能正确处理。
