• As far as I know, the simple DP or recursion solution can not solve this test case.

``````[1,1073741813]
1073741823
Result: 12
``````

Basically, when I saw this problem, I can't assume that the target is small enough to use DP.
It is quite normal if there is a test case like this:

``````[1]
1073741823
Result: 1
``````

Simple recursion can't solve this test case too.
Fortunately, I noticed the return value of method is 'int', so I can assume that the test case like this will not happen:

``````[1,2]
1073741823
Result: int: out of range
``````

Then the idea comes out. Basically this is the permutation problem, code need to count all the possible result and get the answer. But if the code can find all the combinations, the answer still can be calculated.

Here is code, I did some optimizations but it is far from perfect:

``````public class Solution {

int[] nums;
HashMap<ArrayList<Integer>, Integer> st;

public int combinationSum4(int[] ns, int target) {
if (ns == null || ns.length == 0) return 0;

Arrays.sort(ns);
nums = ns;
st = new HashMap<>();
return subSums(ns.length, target, 0);
}

protected int comb(int a, int b) {
int N = a + b;
int K = a > b ? b : a;
int r = 1;
for (int i = 1 ; i <= K ; i++) {
r *= N - i + 1;
r /= i;
}
// System.out.println("C(" + K + "," + N + ")=" + r);
return r;
}

protected int subSums(int arraySize, int target, int lineSize) {
if (target == 0) return 1;
if (arraySize == 1) {
if (target % nums[0] == 0) return comb(lineSize, target / nums[0]);
return 0;
}

ArrayList<Integer> key = new ArrayList<>();

if (st.containsKey(key)) {
return st.get(key);
}

int tot = 0, newItem = 0, factor = 1;
while (target >= 0) {
int now = subSums(arraySize - 1, target, lineSize + newItem);
tot += factor * now;
target -= nums[arraySize - 1];
newItem++;
factor *= lineSize + newItem;
factor /= newItem;
}

st.put(key, tot);