How do you find a subarray with the given sum?

Question

I am given an array of elements and the sum K, and I am supposed to find a subarray (doesn’t have to be contiguous) whose sum is equal to K.

For example: Input: [1, 9, 3, 2, 21], 30 Output: [9, 21]

Do I need to use backtracking or is there another algorithm using dynamic programming for example?

Welcome to [Stack Overflow.](https://stackoverflow.com/ "Stack Overflow") Please be aware this is not a code-writing or tutoring service. We can help solve specific, technical problems, not open-ended requests for code or advice. Please edit your question to show what you have tried so far, and what specific problem you need help with. See the [How To Ask a Good Question](https://stackoverflow.com/help/how-to-ask "How To Ask a Good Question") page for details on how to best help us help you. — itprorh66, Nov 25 '21 at 13:26
Have a look at this wikipedia page: https://en.wikipedia.org/wiki/Subset_sum_problem — Riccardo Bucco, Nov 25 '21 at 13:26

score 1 · Answer 1 · answered Nov 25 '21 at 13:28

1

If it's not a big array you could use brute force: 2^n solutions!

answered Nov 25 '21 at 13:28

mathieu.letombe

343
1
6

score 0 · Answer 2 · answered Nov 25 '21 at 13:49

I can provide the solution, using C++.

//Input: [1, 9, 3, 2, 21],
//resultingSum=30,
//Output: [9, 21].
#include <iostream>
#include <vector>
#include <set>
using namespace std;
const int maximumSize=40;
vector<int> visited(maximumSize, 0);
vector<int> numbers={1, 9, 3, 2, 21};
int resultingSum=30;
set<int> resultingSet;
void showContentVector(vector<int>& input)
{
    for(int i=0; i<input.size(); ++i)
    {
        cout<<input[i]<<", ";
    }
}
void showContentSet(set<int>& input)
{
    for(auto iterator=input.begin(); iterator!=input.end(); ++iterator)
    {
        cout<<*iterator<<", ";
    }
    return;
}
void dfs(int current, int previous)
{
    if(visited[current]==1)
    {
        return;
    }
    visited[current]=1;
    for(int next=0; next<numbers.size(); ++next)
    {
        if(next==current)
        {
            continue;
        }
        if((numbers[current]+numbers[next])==resultingSum)
        {
            resultingSet.insert(numbers[current]);
            resultingSet.insert(numbers[next]);
        }
    }
    for(int next=(current+1); next<numbers.size(); ++next)
    {
        if(next==previous)
        {
            continue;
        }
        dfs(next, current);
    }
    return;
}
int main()
{
    dfs(0, -1);
    showContentSet(resultingSet);
    return 0;
}

Here is the result:

9, 21,

How do you find a subarray with the given sum?

2 Answers2