本文共 995 字，大约阅读时间需要 3 分钟。
Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.
Example:
nums = [1, 2, 3]
target = 4The possible combination ways are:
(1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1)Note that different sequences are counted as different combinations.
Therefore the output is 7.
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/combination-sum-iv 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。dp[i]表示和为i的数量，4，则为单个数字，加上其他的组合数
class Solution { public int combinationSum4(int[] nums, int target) { int[]dp = new int[target + 1]; Arrays.sort(nums); dp[0] = 1; for (int i = 1; i <= target; i++) { int num = 0; for (int j = 0; j < nums.length; j++) { if (nums[j] <= i) { num += dp[i - nums[j]]; } else break; } dp[i] = Math.max(dp[i], num); } return dp[target]; }}