377. 组合总和 Ⅳ

给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。

题目数据保证答案符合 32 位整数范围。

题解

class Solution {
   
   int[] memo;
    public int combinationSum4(int[] nums, int target) {
        if(nums.length==1 && nums[0]>target) return 0;
        
        memo=new int[target+1];
        Arrays.fill(memo,-1);
        memo[0]=1;

       return backtrack(nums,target);
        

    }
    
    public int backtrack(int[] nums, int target){
        //递归出口
        if (memo[target] != -1) {
            return memo[target];
        }
       

        int res=0;
        for(int i=0;i 
注意：本题如果单纯的利用回溯，会出现超时。新学到处理方式：创建一个数组用于记录之前计算的结果，我们如果直接去数组里面找对应结果数即可。
 
数组的大小为target+1，并且除了首位元素为0，其余全部初始化为-1。
 
递归的出口是记录数组的元素不为-1，返回该元素值。当遍历完整个nums数组时，将结果放到记忆数组对应位置，并返回。