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?

Answer 1

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>?

Answer 2

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.