Code optimization subset sum

Question

Here is my code that print elements of subset whose sum is equal to the given sum,(it works only for positive numbers):

#include <bits/stdc++.h>
using namespace std;

void traverse(vector<int> vec) {
    for(int a=0; a < vec.size(); a++)
        cout << vec[a] << " ";
    cout << endl;
}

void possible(vector<int> vec, int sum, vector<int> now) {
    if(sum == 0) {
        traverse(now);
    }
    else if(sum < 0) {
        now.clear();
    }
    else if(sum > 0 && vec.size() > 0) {
        for(int a = 0; a < vec.size(); a++) {
            now.push_back(vec[a]);
            vector<int> vecc(vec.begin() + a + 1, vec.end());
            possible(vecc, sum - vec[a], now);
            now.erase(now.end() - 1);
        }
    }
}

int main() {
    int n, sum;
    cin >> n >> sum;

    vector<int> vec(n), now;
    for(int a = 0; a < n; a++)
        cin >> vec[a];

    possible(vec, sum, now);
    return 0;
}

Is there any chance of improvements or any faster way to improve run time?

Any Dynamic problem solution for this?

The better site to ask for improvements of working code is [SE Code Review](https://codereview.stackexchange.com/). — user0042, Sep 06 '17 at 06:37
Off topic: [Why should I not #include ?](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h) When combined with `using namespace std;` pretty much the entire standard library is pulled into the global namespace. This results in a minefield of identifiers your code may run into. — user4581301, Sep 06 '17 at 06:55

gsamaras · Answer 1 · 2017-09-06T07:24:52.650

Subset Sum Problem can be approached via Dynamic Programmning, as you can read in Dynamic Programming | Set 25 (Subset Sum Problem).

The problem is in-fact NP-Complete (There is no known polynomial time solution for this problem). The link above offers two solutions, where the second one can solve the problem in Pseudo-polynomial time.

As a technical optimization, you could change this:

void traverse(vector<int> vec)

to this:

void traverse(vector<int>& vec)

in order to avoid unnescairy copies of, potentially large, vectors. Do that for all your functions, if you can.

Compile your code with warnings enabled (e.g. -Wall -Wextra for GCC), and fix those warnings. Then consider performance.

PS: Why should I not #include <bits/stdc++.h>?

Mikhail · Accepted Answer · 2019-11-11T06:37:50.453

A recursive dynamic programming solution that seems to work (though I have not tested it thoroughly). It also works with negative numbers.

// To make it simple, returns empty vector if no solution was found
// and also if the sum is zero
std::vector<int> find(const std::vector<int>& numbers, int sum)
{
    std::vector<int> result;
    if (findNumbersMakingSum(numbers, sum, result, 0)) {
        return result;
    } else {
        return std::vector<int>();
    }
}

bool findNumbersMakingSum(
    const std::vector<int>& numbers,
    int sumLeft,
    std::vector<int>& takenNumbers,
    size_t position)
{
    if (!sumLeft) {
        // We're done
        return true;
    }

    if (position == numbers.size()) {
        return false;
    }

    int current = numbers[position];
    if (!current) {
        // Just skip zero elements
        return findNumbersMakingSum(numbers, sumLeft, takenNumbers, position + 1);
    }

    // Case 1: take number at current position:
    takenNumbers.push_back(current);
    if (findNumbersMakingSum(numbers, sumLeft - current, takenNumbers, position + 1)) {
        return true;
    }

    // Case 2: don't take number at current position
    takenNumbers.pop_back();
    return findNumbersMakingSum(numbers, sumLeft, takenNumbers, position + 1);
}

Since it is recursive, with large inputs it will fail because of limited call stack. The solution can be easily updated to not use recursion, but I hope the idea is clear.

score 0 · Answer 3 · answered Sep 06 '17 at 06:35

A dynamic programming solution is mentioned in this Wikipedia article on the Subset Sum problem; it uses 'combinatorialization' of the target value by obtaining two axes for the state space. The first axis is the initial interval of items while the second axis is the desired target value.

Code optimization subset sum

3 Answers3