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 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];
}
''''