Sum It Up (Recursion and Backtracking)

#1

My code----> https://ide.codingblocks.com/s/64540
my code is not giving any output…please check and point out the mistake.

QUES:
SUM IT UP
You are given an array of numbers and a target number(T) , print all unique combinations in the array whose sum equals the target number T. Note that each number in the array may only be used once in the combination.
Note:

All numbers (including target) will be positive integers
Elements in the combination must be in non-descending order
There should be no duplicate combinations
Input Format:
The first line will contain N indicating the number of elements in the array.
The second line will contain space separated N integers , A[i].
The third line will contain the target number T.

Constraints:
N <= 15 1<= A[I] <= 100

Output Format
Print all unique combinations of the numbers satisfying the above constraints in a separate line in lexicographic manner.

Sample Input
7
10 1 2 7 6 1 5
8
Sample Output
1 1 6
1 2 5
1 7
2 6

#2

base case condition are wrong
it is simple
just make the subarray and then when base condition hit that is begining>end of array then sum up and then check if it is equal print it

#3

check this
https://ide.codingblocks.com/s/64795

#4

do we need to backtrack…Here we are generating all the subsets and then checking its sum to match with target…how can we use backtracking for those cases which will not proceed toward the answer and so reducing the number of calls…since all the numbers are positive…if at any point the sum of elements of subset exceeds the target…we should not continue further for that case…

#5

Your code output:
1 2 5
1 7
1 6 1
2 6
2 1 5
7 1

expected output:
1 1 6
1 2 5
1 7
2 6

#6

pratyush we can’t derease the call as two are important for all subset
for the ascending order just sort the array
and for removing duplicates there are many ways i have use one
check this https://ide.codingblocks.com/s/65113

1 Like
#7

can you explain the part how you used map for removing duplicates.

#8

Can someone please check my code, 2 test cases are not working on submitting the code. I’m pretty confident though that it’s correct.
Here is my code-