首页 > > 程序设计 > C/C++ >

377. Combination Sum IV

2018-06-17 23:57:07来源：未知阅读 ()

问题

　　Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.

　　Example:

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

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

　　Note that different sequences are counted as different combinations.

　　Therefore the output is 7.

分析
　　根据题意，子问题可表示为 F(i) = F(i) + F(i - nums[j]),其中 i从1开始到target，j为数组下标，从0到nums.size()。通过计算可得，target为[1,target]的所有最大组合数，计算每个target用的是穷举遍历每个nums元素。

代码

    int combinationSum4(vector<int>& nums, int target) {
        vector<int> V(target + 1 ,0);
        int i,j;
        
        V[0] = 1; //V[0]为1是因为i-nums[j] = 0 时 V[i-nums[j]] 成功一次
        for(i = 1;i <= target; i++)
        {
            for( j = 0; j < nums.size(); j++)
                if(nums[j] <= i)
                    V[i] += V[i - nums[j]];
        }
        
        return V[target];
    }