Subset Sums

Problem

Given a list arr of N integers, print sums of all subsets in it.

Solution Approach

Iterate overall possible subset. This can be done using recursion or bitmasking.

Expected Time complexity: $O(2^n)$

Click - to see solution code

C++

class Solution {
   public:
    vector<int> subsetSums(vector<int> arr, int N) {
        vector<int> ans;
        int end = pow(2, N), sm = 0;
        for (int i = 0; i < end; i++) {
            sm = 0;
            for (int j = 0; j < N; j++) {
                int bit = (1 << j) & i;
                if (bit) sm += arr[j];
            }
            ans.push_back(sm);
        }
        return ans;
    }
};