Combination Sum IV

https://leetcode.com/problems/combination-sum-iv/description/

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.

Thoughts

因为要重复从nums挑选，开始没想到怎么用递推实现。DFS的比较直观，先实现一个brute force的，然后再看那些结果可以重复利用的。

Code

class Solution {
    Map<Integer, Integer> results = new HashMap<>();
    public int combinationSum4(int[] nums, int target) {
        if (results.keySet().contains(target)) {
            return results.get(target);
        }
        if (target < 0) {
            return 0;
        }
        int n = nums.length;
        int res = 0;
        for (int i = 0; i < n; i++) {
            boolean valid = true;
            if (target - nums[i] == 0) {
                res++;
            } else {
                res += combinationSum4(nums, target - nums[i]);
            }         
        }
        results.put(target, res);
        return res;
    }
}

Ver.2

与 传统完全背包问题不同的在于它实际上 不是求combination, 而是类似permutation的数目,.

因为它要求(2, 1, 1)和(1, 1, 2)是两个结果.

如果按照完全背包写法, 是不会出现(2, 1, 1)的情形的, 因为nums[i] =1的情形已经过去了.

解决方法是把完全背包的两个循环颠倒写, 把记录value的j放到外循环, 把记录index的i放到内循环.

class Solution {
    public int combinationSum4(int[] nums, int target) {
        int[] f = new int[target + 1];
        f[0] = 1;
        for (int j = 1; j <= target; j++) { 
            for (int i = 0; i < nums.length; i++) { 
                if (j - nums[i] >= 0) {
                    f[j] += f[j - nums[i]];
                }
            }
        }
        return f[target];
    }
}