377. 组合总和IV

完全背包

class Solution {
    public int combinationSum4(int[] nums, int target) {

        /**
         * dp[i]定义为总和为i时排列的数量
         * 初始dp[0] == 1
         */
        int[] dp = new int[target + 1];
        dp[0] = 1;

        /**
         * 完全背包中，每个数字可以重复使用
         * 因此内循环要从小到大遍历
         * 对于求组合数，dp[i]（考虑nums[j]的组合总和）就是所有的dp[i - nums[j - 1]]（不考虑nums[j]）相加
         * 如果求组合数就是外层for循环遍历物品，内层for遍历背包
         * 如果求排列数就是外层for遍历背包，内层for循环遍历物品
         */
        for (int i = 0; i <= target; i++) {

            for (int j = 1; j <= nums.length; j++) {

                if (i >= nums[j - 1]) {
                    dp[i] += dp[i - nums[j - 1]];
                }
            }
        }

        return dp[target];
    }
}

/**
 * 时间复杂度 O(target*n)
 * 空间复杂度 O(target)
 */

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