LeetCode 377. Combination Sum IV

Problem

LeetCode 377. Combination Sum IV

1. 题目简述

给出一个无重复的正整数数组nums，一个目标数target，找出和为target的所有可能的组合，每个数字可以取多个。例如：

Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
[7],
[2,2,3]
]

2. 算法思路

回溯

那么我们应该使用什么算法呢？还是回溯么？貌似是可行的，只要将循环时的startIndex不设置为i，始终设置为0即可。代码放在下面（实际上会TLE）。

DP

这道题是combination sum系列的第四题，又是不重复的数字，每个数字可以多次，和combination sum I很像，但是1中要求不能有重复的组合([1, 2, 3]和[3, 2, 1]算一种)，而4中即使是相同的数字，不同的排列组合也算不同。例如，我们希望用[1, 2, 3]组合得到7，对于[1, 1]和[2]来说，其实目标都是找出组合为5的所有可能的排列组合的可能性，重复计算，数字越大，重复计算越多，所以DP才是相对较好的解。

3. 解法

1. 回溯。会TLE，原因在于这相当于是一个排列组合问题，由[1, 2, 3]组成30的可能性已经有53798080种，而这其中的每一种都是由好多层递归来实现的，重叠子问题计算得太多。

class Solution {
    int res = 0;
    public int combinationSum4(int[] candidates, int target) {
        Arrays.sort(candidates);

        backtracking(candidates, target, 0, 0);

        return res;
    }

    private void backtracking(int[] candidates, int target, int sum, int startIndex) {
        for (int i = startIndex; i < candidates.length; i++){
            sum += candidates[i];

            if (sum < target) {
                backtracking(candidates, target, sum, 0);
                sum -= candidates[i];
                continue;
            } else if (sum == target) {
                res++;
            }
            return;
        }
    }
}

2. DP。顺利通过。

class Solution {

    int[] dp;
    public int combinationSum4(int[] candidates, int target) {
        // 这里无需像之前那样进行排序，因为这次不需要对不同的顺序有要求，不同顺序也被当成不同个解。
        // Arrays.sort(candidates);
        dp = new int[target + 1];
        Arrays.fill(dp, -1);
        dp[0] = 1;

        return findSum(candidates, target);
    }

    private int findSum(int candicates, int target) {
        if (target < 0) {
            return 0;
        }
        if (dp[target] != -1) {
            return dp[target];
        }

        for (int num : candidates) {
            dp[target] += find(candidates, target - num);
        }

        dp[target]++;// 注意，由于初始值是-1.所以这里要加1

        return dp[target];
    }
}