Subset Sum (without Repetition)

Dynamic Programming

C++ Code

An algorithm that solves the subset sum problem, which involves finding out whether a given set of numbers (without repetition) can add up to a given target value. The program uses a technique called dynamic programming to solve the problem efficiently. It initializes a 2D array to keep track of the subproblems that have already been solved and then recursively checks whether a subset of the numbers can sum up to the target value by either including or excluding each number in the subset.

Time Complexity: O(NS), where N is the target and S is the number of values in the set

        int **mem;
        
        // without repetition
        bool subset_sum(vector<int> values, int sum, int i)
        {
            if (sum < 0 || i < 0)
            {
                return false;
            }
            else if (sum == 0)
            {
                return true;
            }
            if (mem[i][sum] == -1)
            {
                bool answer = subset_sum(values, sum - values.at(i), i - 1) || subset_sum(values, sum, i - 1);
                mem[i][sum] = answer;
                return answer;
            }
            else
            {
                return mem[i][sum];
            }
        }

        int main()
        {
            vector<int> values = {2, 5, 1, 4};
            int target = 8;
            mem = new int *[values.size() + 1];
            for (int i = 0; i < values.size() + 1; i++)
            {
                mem[i] = new int[target + 1];
                for (int j = 0; j < target + 1; j++)
                {
                    mem[i][j] = -1;
                }
            }
            cout << subset_sum(values, target, values.size() - 1) << endl;
        }