377. Combination Sum IV

,

DFS(TLE)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    private static class Result{
        private int count;
    }

    public int combinationSum4(int[] nums, int target) {
        Result result = new Result();

        Arrays.sort(nums);
        dfs(result, nums, 0, target);
        return result.count;
    }

    private void dfs(Result result, int[] nums, int sum, int target) {
        if (sum == target) {
            result.count++;
            return;
        }

        for (int num : nums) {
            if (sum + num > target) {
                break;
            }

            dfs(result, nums, sum + num, target);
        }
    }
}

DFS(TLE)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int combinationSum4(int[] nums, int target) {
        Arrays.sort(nums);
        return dfs(nums, 0, target);
    }

    private int dfs(int[] nums, int sum, int target) {
        if (sum == target) {
            return 1;
        }

        int count = 0;
        for (int num : nums) {
            if (sum + num > target) {
                break;
            }

            count += dfs(nums, sum + num, target);
        }
        return count;
    }
}

DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    public int combinationSum4(int[] nums, int target) {
        Arrays.sort(nums);
        Map<Integer, Integer> cache = new HashMap<>();
        return dfs(cache, nums, 0, target);
    }

    private int dfs(Map<Integer, Integer> cache, int[] nums, int sum, int target) {
        Integer cachedCount = cache.get(sum);
        if (cachedCount != null) {
            return cachedCount;
        }

        if (sum == target) {
            return 1;
        }

        int count = 0;
        for (int num : nums) {
            if (sum + num > target) {
                break;
            }

            count += dfs(cache, nums, sum + num, target);
        }
        cache.put(sum, count);
        return count;
    }
}

DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public int combinationSum4(int[] nums, int target) {
        Map<Integer, Integer> cache = new HashMap<>();
        return dfs(cache, nums, 0, target);
    }

    private int dfs(Map<Integer, Integer> cache, int[] nums, int preSum, int target) {
        if (cache.containsKey(preSum)) {
            return cache.get(preSum);
        }

        if (preSum > target) {
            return 0;
        }
        if (preSum == target) {
            // 找到一条和为 target 的路径
            return 1;
        }

        int count = 0;
        for (int num : nums) {
            count += dfs(cache, nums, preSum + num, target);
        }
        cache.put(preSum, count);
        return count;
    }
}

DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int combinationSum4(int[] nums, int target) {
        Arrays.sort(nums);

        // 定义 dp[i] 为总和为 i 的元素组合的个数
        int[] dp = new int[target + 1];
        dp[0] = 1;
        for (int i = 1; i <= target; i++) {
            for (int num : nums) {
                if (i - num >= 0) {
                    dp[i] += dp[i - num];
                } else {
                    break;
                }
            }
        }

        return dp[target];
    }
}

题目仅要求返回组合的个数其实潜在的提醒我们使用动态规划而不是 DFS。

References

377. Combination Sum IV
剑指 Offer II 104. 排列的数目