377. Combination Sum IV--back tracking +map 优化---ing

发布时间：2020-12-14 04:14:58 所属栏目：大数据来源：网络整理

导读：和39.?Combination Sum 不同的是，377 可以把不同排列的解认为是不同解，例如 [1,1,2] 和 [2,1] 是不同解，并且只需要求出解的个数。例如 nums = [1,2,3] target = 4The possible combination ways are:(1,1)(1,2)(1,3)(2,1)(2,2)(3,1) 返回解的个数7即可。

和39.?Combination Sum 不同的是，377 可以把不同排列的解认为是不同解，例如 [1,1,2] 和 [2,1] 是不同解，并且只需要求出解的个数。

例如

nums = [1,2,3]
target = 4

The possible combination ways are:
(1,1)
(1,2)
(1,3)
(2,1)
(2,2)
(3,1)

返回解的个数7即可。

写成如下解法结果正确，但会TLE，并且在递归中返回解的个数，每次 return 1 就好，不能是count++

class Solution {
    public int combinationSum4(int[] nums,int target) {
        
       return dfs( nums,target,0);
        
    }
    
    private int dfs( int[] nums,int target,int sum){
        int count = 0;
        if(sum > target) return 0;
        if(sum == target) {  
            //count++;
            return 1;
        }
        
        for(int i=0; i<nums.length; i++){
               sum+= nums[i]; 
               count += dfs( nums,sum);
               sum-= nums[i];
             
        }
        
        return count;
    }
}

这里拿backtraing 每次把sum += nums[i] 再去掉上一次的 sum -= num[i]

但不是一个好的写法，好的写法是定义 remain ，而不是sum,code 如下，但依然会TLE

class Solution {
    public int combinationSum4(int[] nums,int target) {
        
       return dfs( nums,target);
        
    }
    
    private int dfs( int[] nums,int remain){
        int count = 0;
        if(remain < 0) return 0;
        if(remain  == 0) {
            return 1;
        }
        
        for(int i=0; i<nums.length; i++){
               count += dfs(nums,remain - nums[i]); 
        }
        
        return count;
    }
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!