Untitled

// Recursive - Entry function
vector<int> subsetSums(vector<int> arr, int N)
{
    vector<int> res;
    subsetSumsUtil(arr, N, res, 0, 0);
    return res;
}

void subsetSumsUtil(vector<int> &arr, int N, vector<int> &res, int i, int sum) {
    if (i == N) {
        res.push_back(sum);
        return;
    }
    
    // Not pick the element at index i
    subsetSumsUtil(arr, N, res, i+1, sum);
    
    // Pick the element at index i
    subsetSumsUtil(arr, N, res, i+1, sum + arr[i]);
}    




// Iterative
vector<int> subsetSums(vector<int> arr, int N)
{
    vector<int> res;
    res.push_back(0);
    
    // Sum of all possible combinations from A[0 .... i] = 
    //      sum of all possible combinations from A[0 ... i-1] 
    //      & (A[i] + sum of all possible combinations from A[0 ... i-1])
    for (int i = 0; i < N; i++) {
        int resSz = res.size();
        for (int j = 0; j < resSz; j++)
            res.push_back(res[j] + arr[i]);
    }
    
    return res;
}