377. 组合总和 Ⅳ (opens new window)

1.记忆化搜索

分析：每种组合打乱顺序后会被视作是新的组合，因此每个节点搜索时数组都需要从头遍历。

不同节点只要当前和相等，那么它们的搜索子树也是完全相同，因此搜索Cache保存当前和为sum下能够到达target的方案数。

class Solution {
    Map<Integer,Integer>map=new HashMap<>();
    public int combinationSum4(int[] nums, int target) {
        Arrays.sort(nums);
        map.put(target,1);
        return dfs(nums,target,0);
    }
    public int dfs(int[] nums,int target,int sum){
        if(map.containsKey(sum)) return map.get(sum);
        int res=0;
        for(int i=0;i<nums.length;i++){
            if(sum+nums[i]>target) break;;
            res+=dfs(nums,target,sum+nums[i]);
        }
        map.put(sum,res);
        return res;
    }
}

2.二维动规+完全背包+全排列

根据上面记忆化搜索可以反推出二维动规的写法，核心就是统计当前和sum的方案数时，它的结果应该等于数组nums中每个数插入后转化为sum的状态数之和。

定义dp[target+1][nums.length]：插入nums[j]后总和转化为target的所有方案数。它的状态转移方程如下：。它等于总和达到i-nums[j]的所有状态数之和。

开辟一个List保存前面计算过的每个总和的状态数之和。

class Solution {
    public int combinationSum4(int[] nums, int target) {
        int[][] dp=new int[target+1][nums.length];
        List<Integer> cache=new ArrayList<>();
        dp[0][0]=1;
        cache.add(1);
        for(int i=1;i<=target;i++){
            int temp=0;
            for(int j=0;j<nums.length;j++){
                if(i-nums[j]>=0){
                    dp[i][j]=cache.get(i-nums[j]);
                    temp+=dp[i][j];
                }
            }
            cache.add(temp);
        }
        return cache.get(target);
    }
}

3.优化为一维滚动数组

直接令dp[i]等于总和为 i 下的所有状态数之和：

class Solution {
    public int combinationSum4(int[] nums, int target) {
        int[] dp=new int[target+1];
        dp[0]=1;
        for(int i=1;i<=target;i++){
            for(int j=0;j<nums.length;j++){
                if(i-nums[j]>=0){
                    dp[i]+=dp[i-nums[j]];
                }
            }
        }
        return dp[target];
    }
}