I was solving the subset-sum problem. There are many ways to solve the problem but I prefer the bitmask approach which is explained here. Now If I want to get the index of the elements that form my given sum X how could I do that.
For example, let's take an array [1,2,3] and given sum = 5 then I could use bit masking to tell that there is a subset with a given sum of 5 in the array. But I was wondering if it's possible to generate the indices which will result in the given sum that is 1 and 2 in our case.
My approach: I can convert the problem to a matrix of array elements and use Dynamic Programming to generate all possible sums then for a given sum then I could perform backtracking to get the indices. But my concern is that this consumes a lot of memory and will be inefficient. So, is there a way to do the same through the bit masking?
PS: Please feel free to edit my question as I am new here, Also please let me know if the solution could exist or not as this concept is just an optimization technique I was thinking about and I am not sure if it could be implemented.