CODEWITHSUNDEEP
c++data-structures
FocusBTW.
FocusBTW.

Reputation: 9

Is there a way that my program can make subsets of any given size?

I have to make subsets of an array and add them individually ({1,2} = 1+2). If I get the result match with user input (con), the output will be YES or NO.

Now the problem I am facing is I don’t know how much size the user will input. If he/she puts in that the size of the array is 4, 4 loops will be needed. Is there any one my subset program works on every size of array?

#include <iostream>

using namespace std;
bool Check(int arr[], int size, int con)
{
    for (int i = 0; i < size; i++)
    {
        if (arr[i] == con)
        {
            return true;
        }
        for (int j = i+1; j < size;j++)
        {
            if (arr[i]+arr[j] == con)
            {
                return true;
            }
            for (int k = j + 1; k < size; k++)
            {
                if (arr[i] + arr[j] + arr[k] == con)
                {
                    return true;
                }
                for (int l = k + 1; l < size;l++)
                {
                    if (arr[i] + arr[j] + arr[k] + arr[l] == con)
                    {
                        return true;
                    }
                }
            }
        }
    }
}


int main()
{
    int size;
    int con;
    cout << "Enter desire size of array" << endl;
    cin >> size;
    cout << "ENter number" << endl;
    cin >> con;
    int *arr = new int[size];
    for (int i = 0; i < size; i++)
    {
        cin >> *(arr + i);
    }
    if (Check(arr, size, con) == true)
    {
        cout << "YESSS!!";
    }
    else
    {
        cout << "NOOO!!";
    }
}

Upvotes: 0

Views: 183

Answers (1)

scohe001
scohe001

Reputation: 15446

Here's a simple example of a recursive implementation of your function:

bool Check(int *arr, int size, int con, int curr_sum = 0)
{       
    for (int i = 0; i < size; i++)
    {
        int new_sum = curr_sum + arr[i];
        if (new_sum == con
            || Check(arr + i, size - i, con, new_sum))
        {
            return true;
        }
    }
    return false;
}

Here's how it works...

We pass around a curr_sum parameter that holds the sum from the parent recursion. The current recursion will go through adding all of its indexes to it, looking for curr_sum + arr[i] == con. If it doesn't, then we'll take the new sum (curr_sum + arr[i]) and put it through another round of recursion starting on the index after the one we're currently looking at.

BEWARE: this is an O(n^2) implementation that you're working with, so it'll be extremely slow (and since this is recursion, liable to stack overflow) as you deal with larger sized arrays.

Upvotes: 2

Related Questions