[Leetcode]377. Combination Sum IV(C++)

题目描述

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.

例子

例子 1

Input: nums = [1, 2, 3], target = 4 Output: 7 Explanation: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.

Follow Up

What if negative numbers are allowed in the given array? How does it change the problem? What limitation we need to add to the question to allow negative numbers?

解题思路

这道题同样可以使用回溯法的思想来求解，可以参考 [Leetcode]40. Combination Sum II(C++)。但注意这次题目中并没有特别指出数据规模，可以理解为这道题还能别的更高效的做法求解（实际上用回溯会超时）。这里用于已经限定了数组中数据都为正数，并且没有没有重复数字，因此我们可以考虑以下思路：

使用记忆化的动态规划，需要求解的子问题为：对于 nums 数组，子集和 i 的数量有多少？这里我们只需要求解 target 个子问题，具体如下：
i == 0 时，有且只有一个可能性既空集，因此 memo[0] = 1
此外对任意 i，我们只需要遍历一遍数组，对每一个元素 num：
- 假如 i >= num, 那么 memo[i] 除了原有结果以外还可以加上所有 memo[i - num] 的结果（只需要在那些子集中加入 num 即可满足条件）
- 注意这里我们之所以可以这么做基于题目给的两个条件：
  - 每个数字可以重复使用，因此 memo[i - num] 中包含 num 也不影响结果
  - 每个数字都是唯一的，这意味着每次遍历 nums 时，我们添加进来的新子集都是唯一的，不会有重复
最后返回 memo[target] 即可

代码如下：

#include <vector>

class Solution {
public:
    int combinationSum4(std::vector<int>& nums, int target) {

        // memo[idx] = n means there are n subsets of nums sum up to idx
        std::vector<unsigned long> memo(target + 1, 0);

        // only empty set sums up to 0
        memo[0] = 1;

        // iterate each target
        for (int i = 0; i <= target; i++) {
            // for each target iterate all num in nums and
            // use memo to find the result of current target
            for (const int& num: nums) {
                // if current target is greater than num
                // then memo[i] could use all subsets belong to the memo[i - m] and add num
                if (i >= num) {
                    memo[i] += memo[i - num];
                }
            }
        }

        return memo[target];
    }
};

对于 Follow up 中的问题：

假如给定数组中有负数，这意味着：
- 求解的子问题不只有 n 个，因为子集和为负数的情况下也有可能被使用
- 我们需要改变题目条件，使每个数字只能使用一次，否则假如 [-1,1], target = 0 的情况下，答案是无穷多个
- 如果每个数字只能使用一次的话，使用回溯法求解即可（如果用动态规划的话，那么求解的子问题是从数组中最小的和（所有负数相加）到最大可能的和（所有正数相加））然后同样思路求解应该也可以。

时间复杂度: O(target * n)
空间复杂度: O(target)

GitHub 代码同步地址： 377.CombinationSumIv.cpp

其他题目： GitHub: Leetcode-C++-Solution 博客： Leetcode-Solutions