How can I find whether sum of any N (not necessarily distinct) elements in array is equal to given element k?
Search Sum of Subset algorithm on Gfg
It’s a classic problem, You can read about it here:
2 Likes
for example k = 12, N = 4 and array = [1,2,3,4,5,6,7,8,9,10,11,12]
then, a possible answer could be:
2 2 4 4
or 2 3 3 4
or 4 4 4 0
It uses distinct elements i think. let me search again
Thanks
No, sir. You’re welcome
1 Like
Also, just to be clear, I want all possible cases (not the count, or True/False) but an array of arrays if you could please tell. Also @sameer_bamanha i looked at the gfg code, and it’s using set() but i needed with repetition allowed. I will try to tweak the code myself but please tell in case i am unable to.
Here, even 3 3 3 or 2 2 2 3 could be a possible solution depending on the value of N (number of terms required)
If repetitions are allowed, Then this method won’t work because the link which i have provided is based on 0-1 knapsack and that too bounded but when repetitions are allowed you can’t possibly use this approach. I saw this kind of problem in Code with demoralizer’s Video, He was describing his Uber Interview Experience he was given the exact same problem and Used Backtracking to solve it, You can find the Pseudo code in the video.
Link to the video: Uber Intern Hiring Experience | Online Coding Round and Interview - YouTube
So Yes, You should try using Backtracking.
1 Like
okay thanks 