377. 组合总和 Ⅳ

古城微笑少年丶 2022-11-29 11:47 103阅读 0赞

给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。

示例:

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

所有可能的组合为：  
(1, 1, 1, 1)  
(1, 1, 2)  
(1, 2, 1)  
(1, 3)  
(2, 1, 1)  
(2, 2)  
(3, 1)

请注意，顺序不同的序列被视作不同的组合。

因此输出为 7。

来源：力扣（LeetCode）  
链接：[传送门][Link 1]  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

超时dfs：

class Solution {
        
    public:
        void dfs(vector<int>& nums, int target, int& count){
        
            if(target < 0) return;
            for(auto num : nums){
        
                if(num < target){
        
                    dfs(nums, target - num, count);
                }else if(num == target) {
        
                    count++;
                }else break;
            }
            return;
        }
    
        int combinationSum4(vector<int>& nums, int target) {
        
            if(nums.size() == 0 || target == 0) return 0;
            
            sort(nums.begin(), nums.end());
            int count = 0;
            dfs(nums, target, count);
            return count;
        }
    };

背包问题，动态规划 dp\[i\] += dp\[i-num\] :

class Solution {
        
    public:
        int combinationSum4(vector<int>& nums, int target) {
        
            vector<unsigned long long> dp(target+1, 0);
            dp[0] = 1;
            sort(nums.begin(), nums.end());
            for(int i = 1; i <= target; ++i){
        
                for(auto num : nums){
        
                    if(i >= num) {
        
                        dp[i] +=  dp[i-num];
                    }else break;
                }
            }
            return dp[target];
        }
    };

[Link 1]: https://leetcode-cn.com/problems/combination-sum-iv