377. Combination Sum IV，377combination

377. Combination Sum IV，377combination

問題

　　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.

分析
　　根據題意，子問題可表示為 F(i) = F(i) + F(i - nums[j]),其中 i從1開始到target，j為數組下標，從0到nums.size()。通過計算可得，target為[1,target]的所有最大組合數，計算每個target用的是窮舉遍歷每個nums元素。

代碼　　

int combinationSum4(vector<int>& nums, int target) { vector<int> V(target + 1 ,0); int i,j; V[0] = 1; //V[0]為1是因為i-nums[j] = 0 時 V[i-nums[j]] 成功一次 for(i = 1;i <= target; i++) { for( j = 0; j < nums.size(); j++) if(nums[j] <= i) V[i] += V[i - nums[j]]; } return V[target]; } View Code