377. Combination Sum IV

I don’t have any clue when I first saw this problem. I followed the top rated solution. The solution has similary idea with problem "322. Coin Change". The idea is to let dp[i] to be the maximal combinations for target i. Note only when nums[j] <= target, nums[j] is a candidate for the combination and the number of combinations with this candidate nums[j] is dp[target-nums[j]]. And also for the target, we need to sum up all the combinations with candidates nums[j] less or equal than the target, so we have
dp[i] = sum of dp[i-nums[j]] where nums[j] <= i.

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