leetcode 377 Combination Sum IV
z
 2019-04-09 10:36:27  

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.

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?

Credits:
Special thanks to @pbrother for adding this problem and creating all test cases.

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class CombinationSumIV {
  /*
  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:

  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.
   */


  // 可以，但是太耗时了。
  static int count = 0;
  public static int combinationSum4(int[] nums, int target) {
    List<ArrayList<Integer>> ans = new ArrayList<>();
    ArrayList<Integer> temp = new ArrayList<>();
    dfs(nums, target, temp, 0);
    return count;
  }
  public static void dfs(int[] nums, int target, ArrayList<Integer> temp, int k){
    int sum = 0;
    for (int i: temp){
      sum += i;
    }
    if (sum == target){
      count ++;
      return ;
    }
    else if (sum > target){
      return ;
    }
    else {
      for (int i=0; i<nums.length; i++){
        temp.add(nums[i]);
        dfs(nums, target, temp, k+1);
        temp.remove(temp.size()-1);
      }
    }
  }

  public static int combinationSum4DP(int[] nums, int target){
    if (target == 0){
      return 1;
    }
    int res = 0;
    for (int i=0; i<nums.length; i++){
      if (target > nums[i])
        res += combinationSum4DP(nums, target-nums[i]);
    }
    return res;
  }

  public static int combinationSum4DPII(int[] nums, int target){

    int[] dp = new int[target+1];
    dp[0] = 1;
    for (int sum=1; sum<=target; sum++){
      for (int i=0; i<nums.length; i++){
        if (sum - nums[i] >=0)
          dp[sum] += dp[sum-nums[i]];
      }
    }
    return dp[target];
  }

  public static void main(String[] args){
    System.out.println(combinationSum4(new int[]{1,2,3}, 32));
  }
}