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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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

首先想当然递归, 递归中因为可以重复, i从0开始: TLE. 因为可以看到会有很多permutation，非常费时间；而且用List<List<Integer>>非常耗空间

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) {
        List<List<Integer>> list = new ArrayList<>();
        dfs(list, new ArrayList<>(), nums, target, 0);
        for (List<Integer> l : list) {
            System.out.println(l);
        }
        return list.size();
    }
    
    public void dfs(List<List<Integer>> list, List<Integer> arr, int[] nums, int target, int start) {
        if (target < 0) return;
        else if (target == 0) list.add(new ArrayList<>(arr));
        else {
            for (int i = 0; i < nums.length; ++i) {
                arr.add(nums[i]);
                dfs(list, arr, nums, target - nums[i], i);
                arr.remove(arr.size() - 1);
            }
        }
    }
}

节约时间: Memoization + dfs; memo: HashMap; 而且map存储的是<curSum, tmpRes>, i.e. 实际上是dp的思路, 类似Jumping stairs.

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int combinationSum4(int[] nums, int target) {
        int[] f = new int[target + 1];
        f[0] = 1;
        for (int i = 1; i <= target; ++i) {
            for (int j : nums) {
                if (i >= j) f[i] += f[i - j];
            }
        }
        return f[target];
        
    }
}