Help needed in Combinational Sum IV

general
, , ,
#1

I was solving this problem on Leetcode- Link- Problem . I just thought of variation, “If no duplicates as well as no rearrangements is possible, count total ways to reach the target”. How to solve this? Example(as given in Leetcode]-
[1,2,3], Target=4
[1,1,1,1]
[1,1,2]
[1,3]
[2,2]
So total answer = 4
My code for this problem-

Code 
int combinationSum4(vector<int>& nums, int target) {
    long long dp[target+1];
    dp[0]=1;
    for(int i=1;i<=target;i++){
        dp[i]=0;
        for(int j=0;j<nums.size();j++){
            if(i>=nums[j]){
                dp[i]+=dp[i-nums[j]];
            }
        }
    }
    return dp[target];
}

How to modify the same code to the variant problem?

#2

u want 1 1 2 and 1 2 1 as different ways ?

#3

[2,1,2] is not possible for this I think. But yes, all rearrangement will be considered same.
Like [1,1,2] , [1,2,1], [2,1,1] all are same and will be just considered one way.
To simply say, rearrangements of the same subset is not considered

#4

yeah sry , I edited but still i m not able to understand your doubt

1 Like
#5

Okay, I will explain more clearly.
Take the example as given- [1,2,3] and Target= 4
The possible subsets to reach 4 are as follows-
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(2, 1, 1)
(1, 3)
(3, 1)
(2, 2)
Total possibilities = 7

What I want is rearrangement/permutations of the same subset would not be considered twice.
That is-
Three permutations of the array (1, 1, 2) are possible to reach target-
(1, 1, 2)
(1, 2, 1)
(2, 1, 1)
I will only consider them as a single way and not take 3.
Similarly (3, 1) has two permutations: (3, 1) and (1, 3). I will consider them as only 1.
So overall possibilities are-
(1, 1, 1, 1)
(1, 1, 2) (You can take any one of the permutations, I am considering this)
(1, 3) (You can take any one of the permutations, I am considering this)
(2, 2)
Answer = 4

I think this will be a bit clear

1 Like
#6

just inter change loops

1 Like
#7

Sorry? Couldn’t catch. Can you please explain?

#8 
int combinationSum4(vector<int>& nums, int target) {
    long long dp[target+1] = {0};
    int n = nums.size();
    dp[0]=1;
    for(int i=0; i<n; i++) 
        for(int j=nums[i]; j<=target; j++) 
            dp[j] +=dp[j-nums[i]]; 
    return dp[target];
}
1 Like
#9

I am not getting the correct answer, for even the above sample example.
Can you please check- Code

#10

edited my above code ,

dp[target + 1] = {0};

“https://ideone.com/PByhCr”

1 Like
#11

That was easy. What was your thought process for this? I could not build a conclusion.

#12

try both the codes on pen-paper , u will know what DP[i] means .

1 Like
#13

Okay, thank you so much @ssrivastava990

1 Like