arpan_99's blog

By arpan_99, history, 3 months ago,

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

Input:

N = 2

arr[] = {2, 3}

Output:

0 2 3 5

Expected Time Complexity: O(2^N)

Expected Auxiliary Space: O(2^N)

Code —

class Solution
{

int subset_sum(vector<int> arr, int n, int i, int sum, vector<int> &ans){
if (i == n){
return sum;
}

//including
int x = subset_sum(arr, n, i+1, sum+arr[i], ans);
ans.push_back(x);
int y = subset_sum(arr, n, i+1, sum, ans);
//not including
ans.push_back(y);
}

public:
vector<int> subsetSums(vector<int> arr, int n){
sort(arr.begin(), arr.end());
vector<int> ans;
subset_sum(arr, n, 0, 0, ans);
return ans;
}
};



For Input:

2

1 1

-647528304 -647528304 0 1 1 2

Expected Output:

0 1 1 2

 » 3 months ago, # | ← Rev. 2 →   0 apart from the main bug, an important bug in your code is that you are not using references for passing the array to the function. due to this issue, the auxillary space needed would increase (far more than expected in many cases) to $O(n2^n)$.EDIT: Due to deep copying, the time complexity increases to $O(n2^n)$ as well.
 » 3 months ago, # |   0 on the main bug: I suggest that you draw how the call stack changes in a tree-like structure, and then where each output happens. Here is one way to fix: How to fixmove the lines for pushing the answer into the if statement. You don't really need the return value, we only want the sum of the current set.
 » 2 months ago, # |   0 Your int subset_sum() function is missing a return value, so your code is UB.