Sum It Up- how to solve it using backtracking

#1

First need to find sequence and then sum the elements and if sum is not equal to given sum then we need to set sum to 0 or there should be some another approach?

#2

You need not find subsequence and then find the sum. You can use recursion and backtracking to find the sum

#3

All test cases are not passing

#4

Hi your code is running wrong for input array elements greater than 9.
for e.g.
Consider below TC:
2
10 9
19
Your Output:0 1 9
Desired Output: 9 10

#5

Hi Koshima, Please ask your doubt here if it still persists.

#6

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.

#7

I m still not able to figure out the mistake.

#8

@koshimagoyal97
Hi can you please provide comments with your code i am unable to interpret your code completely.

#9

@mailmeanmolbansal
I have put the comments. Please check it out

#10

@koshimagoyal97
Sorry for the late reply,two of your TC are not giving right answer because we need to print them in desired output,i.e we must print 1 3 3 before 7.
Another e.g: Consider array as
10
7 62 28 73 68 59 21 92 4 97
90
We need to print 7 21 62 before 28 62.
Means the complete Set needs to be print sorted.

#11

@mailmeanmolbansal
After making the changes my code is able to pass the test case you provided but not all the testcases of question.

#12

@koshimagoyal97
Sorry for the late response.
You sdidn’t got what it was demanded in the desired Output and still printing all subsequences correctly but the order which is required is not clear to you.
Let me try again,for
15
57 79 16 3 83 70 78 14 5 8 36 51 47 93 72
86
Your code is printing
5 14 16 51
14 72
8 78
3 5 78
3 5 8 70
3 83
5 8 16 57
16 70
3 36 47
In random Order,but the Output required is in lexographical manner.
Required Output:
3 5 8 70
3 5 78
3 36 47
3 83
5 8 16 57
5 14 16 51
8 78
14 72
16 70

Moreover,you have overkilled your code with the condition if(i>k) and making HashSet of String,because using HashSet of String will make it complicated to handle lexographic manner and will eventually take more time to code during the Interviews.
Let me discuss another approach,
For simplicity the HashSet is used to handle duplicacy,if i remove duplicacy from the array itself before using it further or if I Sort the Array
and check the prev and current element if same i didn’t make any call(Because Sorting made the duplicate elements adjacent).
Now the Array doesn’t contains any duplicates we can just use backtracking and recursion to solve this problem AND coming to the lexo manner,the Arrays.sort is there to handle it.
Please refer this code for the above mentioned approach:

1 Like
#13

@mailmeanmolbansal
Thanks alot. Your explanation not only helped me in understanding my mistakes for this code but also helped me out in understanding the concepts.