0

print all the subsequences having the sum k ? take the array as [2,3,5,1,6,4,7] and k=7....

As backtracking is taking the Time Complexity: O(2^n) and the space complexity of Auxiliary Space: O(h). is there is any way to do it in lower time complexity?

PaulMcKenzie
  • 34,698
  • 4
  • 24
  • 45
secret prasad
  • 11
  • 1
    Do not tag `dsa`. Your question has nothing to do with `Digital Signature Algorithm`. – PaulMcKenzie Aug 12 '23 at 19:11
  • I think you can get faster by sorting and actively searching for matching parts. I don't know how that looks with long sequences, though, but that might be a start – njzk2 Aug 12 '23 at 19:17
  • Your example has the 7 integers from 1-7 in shuffled order. Is it guaranteed that the input will always have 1-n in some order with no integers missing or repeated? – Dave Aug 12 '23 at 20:01
  • 1
    By "subsequence" do you mean adjacent values in the array, i.e., a set with sequential indices? Or are you proposing any subset, regardless of adjacency of the elements? Please address this explicitly by providing the indices of the example array you have identified as solutions for `k=7`. Also, are all values in the array positive (as in your example), or can it contain negative values as well? I believe there's an O(n) solution if the values are all positive and must be adjacent. – pjs Aug 12 '23 at 20:15
  • 1
    If this problem comes from a web page, please provide a link to that page. – Old Dog Programmer Aug 12 '23 at 21:09
  • 1
    [Subset sum](https://en.wikipedia.org/wiki/Subset_sum_problem#Pseudo-polynomial_time_dynamic_programming_solutions). – Stanislav Volodarskiy Aug 12 '23 at 22:20
  • 1
    @StanislavVolodarskiy My concern is that "subset" and "subsequence" can mean two very different things. OP needs to specify the definition they're using. – pjs Aug 12 '23 at 22:49
  • @pjs, OP mentions backtracking which is useless for sub-arrays. – Stanislav Volodarskiy Aug 12 '23 at 22:54

0 Answers0