Combination Sum IV

(Previously Backpack VI on LintCode.)

Problem

Given an integer array nums with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.

Example

Given nums = [1, 2, 4], target = 4

The possible combination ways are:

[1, 1, 1, 1]
[1, 1, 2]
[1, 2, 1]
[2, 1, 1]
[2, 2]
[4]

return 6