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
Your Output:
-647528304 -647528304 0 1 1 2
Expected Output:
0 1 1 2
Please help me understand where are these garbage values coming from (-647528304, -647528304)
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.
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:
move 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.Your
int subset_sum()
function is missing a return value, so your code is UB.