# For the same problem, different sequence of same numbers regarded as one combination.

• For the same problem, different sequence of same numbers regarded as one combination.

For example, [1,2,3] target =4;

different combinations are {
1,1,1,1
1,2,1
2,2
1,3
}

So the output should be 4.

Is any dp solution for this question?

• I don't want the backtracking solution which output all combinations(same as Combination Sum problem), what I need is just the number of combinations.

• I am new to backpack problem. I tried to develop below code and verified by several simple tcs.
Please help me to figure it out right or not. Also, if right, why just simply switch the outer-inner loop then we can get the results where order doesn't matter?

‘’‘
public int makeChange3(int[] nums, int target){
if(target==0) return 1;
int[] dp=new int[target+1];
dp[0]=1;

``````for(int num : nums){
for(int i=1; i<=target; i++){
if(i>=num) dp[i]+=dp[i-num];
}
}
return dp[target];
``````

}
''''

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.